GRAMMARS WITH TIME FUNCTIONS,

Abstract

The subject of this paper is the study of formal grammars and of formal languages from the viewpoint of time-bounded grammars. The principal results focus on properties similar to those of families of languages defined by time-bounded nondeterministic Turing machines. Chapter 1 contains an overview of the results of this paper and a summary of basic ideas of automata theory and mathematical linguistics used here. In Chapter 2, basic properties of time-bounded grammars and languages generated by time-bounded grammars are investigated. Chapter 3 establishes the positive closure and containment properties of families of languages defined by grammars whose time functions are bounded by bounding functions. Nonclosure, undecidability, and hierarchy results are established in Chapter 4. (Author)

Document Details

Document Type
Technical Report
Publication Date
Feb 01, 1969
Accession Number
AD0688147

Entities

People

  • Ronald V. Book

Organizations

  • Harvard University

Tags

DTIC Thesaurus Topics

  • Automata
  • Automata Theory
  • Automatic
  • Computer Languages
  • Formal Languages
  • Grammars
  • Hierarchies
  • Language
  • Linguistics
  • Machines
  • Social Sciences
  • Translations

Fields of Study

  • Mathematics

Readers

  • Computational Linguistics
  • Mathematical Modeling and Probability Theory.