Syntactic complexity of context-free grammars over word monoids
The syntactic complexity of context-free grammars defined over word monoids is investigated. It is demonstrated that every recursively enumerable language can be defined by a ten-nonterminal context-free grammar over a word monoid generated by an alphabet and six words of length two. Open problems a...
|Published in:||Acta Informatica, Vol. 33, No. 5 (1996), p. 457-462|
|QR Code:||Show QR Code|