Prof. RNDr. Alexander Meduna, CSc.

MEDUNA Alexander a ZEMEK Petr. Generalized One-Sided Forbidding Grammars. International Journal of Computer Mathematics. 2013, roč. 90, č. 2, s. 172-182. ISSN 0020-7160. Dostupné z: http://www.tandfonline.com/doi/abs/10.1080/00207160.2012.723703
Jazyk publikace:angličtina
Název publikace:Generalized One-Sided Forbidding Grammars
Název (cs):Zobecněné jednostranné zakazující gramatiky
Strany:172-182
Místo vydání:GB
Rok:2013
URL:http://www.tandfonline.com/doi/abs/10.1080/00207160.2012.723703
Časopis:International Journal of Computer Mathematics, roč. 90, č. 2, GB
ISSN:0020-7160
DOI:10.1080/00207160.2012.723703
Klíčová slova
formální jazyky, řízené přepisování, zobecněné jednostranné zakazující gramatiky, jazykové třídy, generativní síla
Anotace
V zobecněných jednostranných zakazujících gramatikách má každé pravidlo přiřazenu konečnou množinu řetězců a množina pravidel je rozdělena na množiny levě a pravě zakazujících pravidel. Levě zakazující pravidlo může být aplikováno pokud každý z jeho zakazujících řetězců není přítomen vlevo od přepisovaného neterminálu v aktuální větné formě. Pravě zakazující pravidlo je aplikováno analogicky. Mimo tohoto pracují jako zobecněné zakazující gramatiky. V článku jsou dokázány následující tři výsledky. (1) Zobecněné jednostranné zakazující gramatiky, kde každý zakazující řetězec je tvořen nejvýše dvěma symboly, definují třídu rekurzivně spočetných jazyků. (2) Zobecněné jednostranné zakazující gramatiky, kde jedna z množin pravidel obsahuje pouze bezkontextová pravidla bez zakazujících řetězců, definují třídu bezkontextových jazyků. (3) Zobecněné jednostranné zakazující gramatiky, kde je množina levě zakazujících pravidel identická s množinou pravě zakazujících pravidel, definují třídu bezkontextových jazyků.
BibTeX:
@ARTICLE{
   author = {Alexander Meduna and Petr Zemek},
   title = {Generalized One-Sided Forbidding Grammars},
   pages = {172--182},
   journal = {International Journal of Computer Mathematics},
   volume = 90,
 number = 2,
   year = 2013,
   ISSN = {0020-7160},
   doi = {10.1080/00207160.2012.723703},
   language = {english},
   url = {http://www.fit.vutbr.cz/research/view_pub.php.cs?id=9842}
}

Vaše IPv4 adresa: 3.83.192.109
Přepnout na https