Accession Number:

AD0749110

Title:

An Analysis of Grammars by Their Derivation Sets.

Descriptive Note:

Technical rept.,

Corporate Author:

IOWA UNIV IOWA CITY DEPT OF MATHEMATICS

Personal Author(s):

Report Date:

1972-09-01

Pagination or Media Count:

24.0

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

Subject Categories:

  • Linguistics
  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE