Detail publikace

One-Sided Forbidding Grammars and Selective Substitution Grammars

MEDUNA Alexander a ZEMEK Petr. One-Sided Forbidding Grammars and Selective Substitution Grammars. International Journal of Computer Mathematics, roč. 89, č. 5, 2012, s. 586-596. ISSN 0020-7160. Dostupné z: http://www.tandfonline.com/doi/abs/10.1080/00207160.2011.642300
Název česky
Jednostranné zakazující gramatiky a selektivní gramatiky
Typ
článek v časopise
Jazyk
angličtina
Autoři
URL
Klíčová slova

Teorie formálních jazyků, řízené přepisování, jednostranné zakazující gramatiky, selektivní gramatiky, generativní síla

Abstrakt

V jednostranných zakazujících gramatikách je množina pravidel rozdělena na množinu levě zakazujících pravidel a množinu pravě zakazujících pravidel. Levě zakazující pravidlo může přepsat neterminál pokud aktuální větná forma vlevo od přepisovaného symbolu neobsahuje žádný ze zakázaných symbolů. Pravě zakazující pravidlo je aplikováno analogicky, pouze kontrola se provádí doprava místo doleva. Jinak tyto gramatiky pracují stejně jako obyčejné zakazující gramatiky.

V článku je jako hlavní výsledek dokázáno, že jednostranné zakazující gramatiky jsou ekvivalentní selektivním gramatikám. Tato ekvivalence je dokázána jak pro gramatiky připouštějící vymazávací pravidla, tak pro gramatiky bez těchto pravidel. Dále je dokázáno, že jednostranné zakazující gramatiky s množinou levě zakazujících pravidel identickou s množinou pravě zakazujících pravidel generují pouze třídu bezkontextových jazyků. V závěru článku je diskutován význam dosažených výsledků.

Rok
2012
Strany
586-596
Časopis
International Journal of Computer Mathematics, roč. 89, č. 5, ISSN 0020-7160
DOI
UT WoS
000300852300001
BibTeX
@ARTICLE{FITPUB9716,
   author = "Alexander Meduna and Petr Zemek",
   title = "One-Sided Forbidding Grammars and Selective Substitution Grammars",
   pages = "586--596",
   journal = "International Journal of Computer Mathematics",
   volume = 89,
   number = 5,
   year = 2012,
   ISSN = "0020-7160",
   doi = "10.1080/00207160.2011.642300",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/9716"
}
Nahoru