Accession Number : AD0683296

Title :   ON THE COMPLEXITY OF GRAMMARS.

Descriptive Note : Technical rept.,

Corporate Author : IOWA UNIV IOWA CITY DEPT OF MATHEMATICS

Personal Author(s) : Fleck,Arthur C.

Report Date : FEB 1969

Pagination or Media Count : 23

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)

Descriptors :   (*GRAMMARS, CLASSIFICATION), SET THEORY, LANGUAGE, CONTEXT FREE GRAMMARS, CONTEXT SENSITIVE GRAMMARS, COMPUTER PROGRAMMING

Subject Categories : Linguistics

Distribution Statement : APPROVED FOR PUBLIC RELEASE