Journal articleMEDUNA Alexander and ZEMEK Petr. Nonterminal Complexity of OneSided Random Context Grammars. Acta Informatica. 2012, vol. 49, no. 2, pp. 5568. ISSN 00015903. Available from: http://www.springerlink.com/content/5822041380786746/  Publication language:  english 

Original title:  Nonterminal Complexity of OneSided Random Context Grammars 

Title (cs):  Neterminální složitost jednostranných gramatik s nahodilým kontextem 

Pages:  5568 

Place:  DE 

Year:  2012 

URL:  http://www.springerlink.com/content/5822041380786746/ 

Journal:  Acta Informatica, Vol. 49, No. 2, DE 

ISSN:  00015903 

DOI:  10.1007/s0023601201506 

Keywords 

Formal languages, nonterminal complexity, onesided random context grammars, random context nonterminals 
Annotation 

In the present paper, we study the nonterminal complexity of onesided random context grammars. More specifically, we prove that every recursively enumerable language can be generated by a onesided random context grammar with no more than ten nonterminals. An analogical result holds for thirteen nonterminals in terms of these grammars with the set of left random context rules coinciding with the set of right random context rules. Furthermore, we introduce the notion of a right random context nonterminal, defined as a nonterminal that appears on the lefthand side of a right random context rule. We demonstrate how to convert any onesided random context grammar G to an equivalent onesided random context grammar H with two right random context nonterminals. An analogical conversion is given in terms of (1) propagating onesided random context grammars and (2) left random context nonterminals. In the conclusion, two open problems are stated.

BibTeX: 

@ARTICLE{
author = {Alexander Meduna and Petr Zemek},
title = {Nonterminal Complexity of OneSided Random Context Grammars},
pages = {5568},
journal = {Acta Informatica},
volume = {49},
number = {2},
year = {2012},
ISSN = {00015903},
doi = {10.1007/s0023601201506},
language = {english},
url = {http://www.fit.vutbr.cz/research/view_pub.php?id=9714}
} 
