Článek v časopise

 
Meduna, A., Zemek, P.: One-Sided Random Context Grammars, In: Acta Informatica, roč. 48, č. 3, 2011, DE, s. 149-163, ISSN 0001-5903
Jazyk publikace:angličtina
Název publikace:One-Sided Random Context Grammars
Název (cs):Jednostranné gramatiky s nahodilým kontextem
Strany:149-163
Místo vydání:DE
Rok:2011
URL:http://www.springerlink.com/content/c70163w7764u8660/
Časopis:Acta Informatica, roč. 48, č. 3, DE
ISSN:0001-5903
URL:http://www.springerlink.com/content/c70163w7764u8660/ [HTML]
Klíčová slova
Řízené přepisování, gramatiky s nahodilým kontextem, jednostranné varianty, generativní síla, jazykové třídy
Anotace
Článek zavádí jednostranné gramatiky s nahodilým kontextem, což jsou bezkontextové gramatiky, kde je navíc ke každému pravidlu přiřazena množina povolujících neterminálů a množina zakazujících neterminálů. Množina pravidel je u těchto gramatik dále rozdělena na množinu levě nahodilých kontextových pravidel a pravě nahodilých kontextových pravidel. Levě nahodilé kontextové pravidlo může přepsat neterminál ve větné formě pouze tehdy, když se vlevo od něj vyskytují všechny povolující neterminály a všechny zakazujícící neterminály se na tomto místě nevyskytují. Pravě nahodilá kontextová pravidla jsou aplikována obdobně, ovšem s tím rozdílem, že se na výskyt symbolů díváme doprava od přepisovaného neterminálu.

V článku je demonstrováno, že pokud v těchto gramatikách nepřipustíme vymazávácí pravidla, tak definují třídu kontextových jazyků. Při připuštění těchto pravidel definují třídu rekurzivně spočetných jazyků. Je ukázáno, že tyto výsledky platí i v případě, když je množina levě nahodilých kontextovým pravidel totožná s množinou pravě nahodilých kontextových pravidel. Článek dále diskutuje generativní sílu různých speciálních variant těchto gramatik. V závěru jsou zmíněny některé důležité otevřené problémy k budoucímu studiu.
BibTeX:
@ARTICLE{
   author = {Alexander Meduna and Petr Zemek},
   title = {One-Sided Random Context Grammars},
   pages = {149--163},
   journal = {Acta Informatica},
   volume = {48},
   number = {3},
   year = {2011},
   ISSN = {0001-5903},
   language = {english},
   url = {http://www.fit.vutbr.cz/research/view_pub.php?id=9472}
}