Detail publikace

Left Random Context ET0L Grammars

MEDUNA Alexander a ZEMEK Petr. Left Random Context ET0L Grammars. Fundamenta Informaticae, roč. 123, č. 3, 2013, s. 289-304. ISSN 0169-2968. Dostupné z: http://iospress.metapress.com/content/b3h6456215g6754p/?p=e7359885e380461c96f9663f43ae8b09&pi=2
Název česky
Levé ET0L gramatiky s nahodilým kontextem
Typ
článek v časopise
Jazyk
angličtina
Autoři
Meduna Alexander, prof. RNDr., CSc. (UIFS FIT VUT)
Zemek Petr, Ing. (UIFS FIT VUT)
URL
Klíčová slova

Řízené přepisování, ET0L gramatiky, nahodilý kontext, levé varianty, generativní síla, jazykové třídy

Abstrakt

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ů.

Rok
2013
Strany
289-304
Časopis
Fundamenta Informaticae, roč. 123, č. 3, ISSN 0169-2968
Vydavatel
IOS Press
DOI
10.3233/FI-2013-811
BibTeX 
@ARTICLE{FITPUB9741,
   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",
   doi = "10.3233/FI-2013-811",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/9741"
}
Nahoru