Nonterminal complexity of one-sided random context grammars
In the present paper, we study the nonterminal complexity of one-sided random context grammars. More specifically, we prove that every recursively enumerable language can be generated by a one-sided random context grammar with no more than ten nonterminals. An analogical result holds for thirteen no...
|Published in:||Acta Informatica, Vol. 49, No. 2 (2012), p. 55-68|
|Other Involved Persons:|
|QR Code:||Show QR Code|