Detail publikace

One-Sided Random Context Grammars

MEDUNA Alexander a ZEMEK Petr. One-Sided Random Context Grammars. Acta Informatica, roč. 48, č. 3, s. 149-163. ISSN 0001-5903. Dostupné z: http://www.springerlink.com/content/c70163w7764u8660/
Název česky
Jednostranné gramatiky s nahodilým kontextem
Typ
článek v časopise
Jazyk
angličtina
Autoři
URL
Klíčová slova
Řízené přepisování, gramatiky s nahodilým kontextem, jednostranné varianty, generativní síla, jazykové třídy
Abstrakt
Č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.
Rok
2011
Strany
149-163
Časopis
Acta Informatica, roč. 48, č. 3, ISSN 0001-5903
Vydavatel
Springer Verlag
DOI
BibTeX
@ARTICLE{FITPUB9472,
   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",
   doi = "10.1007/s00236-011-0134-y",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/9472"
}
Nahoru