ON THE COMPLEXITY OF GRAMMARS.
Abstract
Grammars are categorized according to the type of the set of all derivations of elements of the language of the grammar. In particular, it is shown that a grammar has a regular set of derivations (is simple if and only if the grammar is nonterminal bounded). Also it is shown that a language is simple if and only if it is meta-linear. Finally, it is shown that for a context-free grammar the set of derivations is always context-sensitive but may not be context-free. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 01, 1969
- Accession Number
- AD0683296
Entities
People
- Arthur C. Fleck
Organizations
- University of Iowa