An Analysis of Grammars by Their Derivation Sets.
Abstract
One of the difficulties in the analysis of context-free grammars (and therefore languages) is the strong combinatorial nature of the mechanism. A measure of this complexity is suggested here. It involves labeling the productions and considering the sequences of labels that correspond to valid derivations. This gives rise to a language and the type of this language is used to categorize the grammar. Results relate these categories to others introduced in the literature, to the generation capacity of the class, and to the use of control sets on grammars. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 1972
- Accession Number
- AD0749110
Entities
People
- Arthur C. Fleck
Organizations
- University of Iowa