Detail publikace

Workspace Theorems for Regular-Controlled Grammars

MEDUNA Alexander a ZEMEK Petr. Workspace Theorems for Regular-Controlled Grammars. Theoretical Computer Science, roč. 412, č. 35, 2011, s. 4604-4612. ISSN 0304-3975. Dostupné z: http://www.sciencedirect.com/science/article/pii/S0304397511003513
Název česky
Workspace věty pro gramatiky řízené regulárním jazykem
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

Bezkontextové gramatiky řízené regulárním jazykem, workspace podmínky, odstraňování vymazávacích pravidel

Abstrakt

Článek ustavuje workspace věty pro (bezkontextové) gramatiky řízené regulárním jazykem. Ukazuje, že pokud pro gramatiku řízenou regulárním jazykem H existuje celé kladné číslo k takové, že H generuje každou větu z L(H) derivací, ve které každá větná forma x obsahuje nejvýše (k-1)|x|/k výskytů neterminálů, které jsou ve zbytku derivace vymazány (|x| označuje délku x), pak L(H) může být generován gramatiku řízenou regulárním jazykem bez vymazávacích pravidel. Analogická věta je demonstrována pro gramatiky řízené regulárním jazykem s kontrolou na výskyt. Článek dává algoritmus pro odstranění vymazávacích pravidel z gramatik řízených regulárním jazykem (eventuálně s kontrolou na výskyt) beze změny generovaného jazyka. V závěru je nastíněn vztah workspace vět k jiným oblastem teorie formálních jazyků.

Rok
2011
Strany
4604-4612
Časopis
Theoretical Computer Science, roč. 412, č. 35, ISSN 0304-3975
Vydavatel
Elsevier Science
DOI
10.1016/j.tcs.2011.04.042
UT WoS
000294031200014
BibTeX 
@ARTICLE{FITPUB9583,
   author = "Alexander Meduna and Petr Zemek",
   title = "Workspace Theorems for Regular-Controlled Grammars",
   pages = "4604--4612",
   journal = "Theoretical Computer Science",
   volume = 412,
   number = 35,
   year = 2011,
   ISSN = "0304-3975",
   doi = "10.1016/j.tcs.2011.04.042",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/9583"
}
Nahoru