Článek v časopise

MEDUNA Alexander a ZEMEK Petr. Left Random Context ET0L Grammars. Fundamenta Informaticae. Amsterdam: IOS Press, 2013, roč. 123, č. 3, s. 289-304. ISSN 0169-2968. Dostupné z: http://iospress.metapress.com/content/b3h6456215g6754p/?p=e7359885e380461c96f9663f43ae8b09&pi=2
Jazyk publikace:angličtina
Název publikace:Left Random Context ET0L Grammars
Název (cs):Levé ET0L gramatiky s nahodilým kontextem
Strany:289-304
Místo vydání:NL
Rok:2013
URL:http://iospress.metapress.com/content/b3h6456215g6754p/?p=e7359885e380461c96f9663f43ae8b09&pi=2
Časopis:Fundamenta Informaticae, roč. 123, č. 3, Amsterdam, NL
ISSN:0169-2968
Klíčová slova
Řízené přepisování, ET0L gramatiky, nahodilý kontext, levé varianty, generativní síla, jazykové třídy
Anotace
Uvažujme ET0L gramatiky. Modifikujme je tak, že ke každému pravidla je přiřazena množina povolujících a zakázaných symbolů, stejně jako tomu je u gramatik s nahodilým kontextem. Takovéto pravidlo může přepsat symbol pouze pokud se všechny symboly z povolující množiny vyskytují vlevo od přepisovaného symbolu a žádný ze zakázaných symbolů se vlevo nevyskytuje. ET0L gramatiky modifikované tímto způsobem jsou nazývány levě nahodile kontextové ET0L gramatiky a jsou hlavním tématem tohoto článku.

Dokazujeme, že tyto gramatiky definují třídu rekurzivně spočetných jazyků. Bez vymazávacích pravidel pak definují třídu kontextovým jazyků. Taktéž zavádíme několik variant těchto gramatik a studujeme jejich generativní sílu. V závěru článku usadíme dokázané výsledky do kontextu teorie formálních jazyků a formulujeme několik otevřených problémů.

BibTeX:
@ARTICLE{
   author = {Alexander Meduna and Petr Zemek},
   title = {Left Random Context ET0L Grammars},
   pages = {289--304},
   journal = {Fundamenta Informaticae},
   volume = {123},
   number = {3},
   year = {2013},
   ISSN = {0169-2968},
   language = {english},
   url = {http://www.fit.vutbr.cz/research/view_pub.php.cs.iso-8859-2?id=9741}
}

Vaše IPv4 adresa: 54.234.0.2
Přepnout na IPv6 spojení

DNSSEC [dnssec]