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) : Fleck,Arthur C.

Report Date : SEP 1972

Pagination or Media Count : 24

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)

Descriptors :   (*CONTEXT FREE GRAMMARS, *MATHEMATICAL LOGIC), SET THEORY, COMBINATORIAL ANALYSIS, PROGRAMMING LANGUAGES, THEOREMS

Subject Categories : Linguistics
      Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE