
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 metalinear. Finally, it is shown that for a contextfree grammar the set of derivations is always contextsensitive but may not be contextfree. (Author)
Descriptors : (*GRAMMARS, CLASSIFICATION), SET THEORY, LANGUAGE, CONTEXT FREE GRAMMARS, CONTEXT SENSITIVE GRAMMARS, COMPUTER PROGRAMMING
Subject Categories : Linguistics
Distribution Statement : APPROVED FOR PUBLIC RELEASE