Publication details
An Improvement of the Descriptional Complexity of Grammars Regulated by Context Conditions
| Authors | |
|---|---|
| Year of publication | 2006 |
| Type | Article in Proceedings |
| Conference | Second Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2006) |
| MU Faculty or unit | |
| Citation | |
| Keywords | descriptional complexity; generalized forbidding grammar; simple semi-conditional grammar |
| Description | This paper improves some well-known results concerning the descriptional complexity of grammars regulated by context conditions. Specifically, it proves that every recursively enumerable language is generated by a generalized forbidding grammar of degree two with no more than eight conditional productions and ten nonterminals, or by a simple semi-conditional grammar of degree (2,1) with no more than nine conditional productions and ten nonterminals. |