An Analysis of Grammars by Their Derivation Sets.
IOWA UNIV IOWA CITY DEPT OF MATHEMATICS
Pagination or Media Count:
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
- Theoretical Mathematics