Detail publikace
One-Sided Forbidding Grammars and Selective Substitution Grammars
Teorie formálních jazyků, řízené přepisování, jednostranné zakazující gramatiky, selektivní gramatiky, generativní síla
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ů.
@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"
}