Detail publikace
Nonterminal Complexity of One-Sided Random Context Grammars
Formální jazyky, neterminální složitost, jednostranné gramatiky s nahodilým kontextem, nahodile kontextové neterminály
V článku je studována neterminální složitost jednostranných gramatiky s nahodilým kontextem. Je dokázáno, že každý rekurzivně spočetný jazyk lze generovat jednostrannou gramatikou s nahodilým kontextem mající nejvýše 10 neterminálů. Analogický výsledek platí pro třináct neterminálů v případě těchto gramatik mající množinu levě kontextových pravidel identickou s množinou pravě kontextových pravidel. Dále je zaveden pojem pravě kontextového neterminálu, který je definován jako neterminál vyskytující se na levé straně některého pravě kontextového pravidla. Článek ukazuje, jak transformovat každou jednostrannou gramatiku s nahodilým kontextem G na ekvivalentní jednostrannou gramatiku s nahodilým kontextem H mající pouze dva pravě kontextové neterminály. Analogický výsledek je dokázán (1) pro jednostranné gramatiky s nahodilým kontextem bez vymazávacích pravidel a (2) pro levě kontextové neterminály. V závěru článku jsou zmíněny dva otevřené problémy.
@ARTICLE{FITPUB9714, author = "Alexander Meduna and Petr Zemek", title = "Nonterminal Complexity of One-Sided Random Context Grammars", pages = "55--68", journal = "Acta Informatica", volume = 49, number = 2, year = 2012, ISSN = "0001-5903", doi = "10.1007/s00236-012-0150-6", language = "english", url = "https://www.fit.vut.cz/research/publication/9714" }