Detail publikace

Generalized One-Sided Forbidding Grammars

MEDUNA Alexander a ZEMEK Petr. Generalized One-Sided Forbidding Grammars. International Journal of Computer Mathematics, roč. 90, č. 2, 2013, s. 172-182. ISSN 0020-7160. Dostupné z: http://www.tandfonline.com/doi/abs/10.1080/00207160.2012.723703
Název česky
Zobecněné jednostranné zakazující gramatiky
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

formální jazyky, řízené přepisování, zobecněné jednostranné zakazující gramatiky, jazykové třídy, generativní síla

Abstrakt

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

Rok
2013
Strany
172-182
Časopis
International Journal of Computer Mathematics, roč. 90, č. 2, ISSN 0020-7160
DOI
10.1080/00207160.2012.723703
BibTeX 
@ARTICLE{FITPUB9842,
   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 = "https://www.fit.vut.cz/research/publication/9842"
}
Nahoru