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):

Report Date:

1969-02-01

Pagination or Media Count:

23.0

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

Subject Categories:

  • Linguistics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE