Detail publikace

Workspace Theorems for Regular-Controlled Grammars

MEDUNA, A.; ZEMEK, P. Workspace Theorems for Regular-Controlled Grammars. Theoretical Computer Science, 2011, vol. 412, no. 35, p. 4604-4612. ISSN: 0304-3975.
Název česky
Workspace věty pro gramatiky řízené regulárním jazykem
Typ
článek v časopise
Jazyk
anglicky
Autoři
Meduna Alexandr, prof. RNDr., CSc. (UIFS)
Zemek Petr, Ing., Ph.D.
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
DOI
10.1016/j.tcs.2011.04.042
UT WoS
000294031200014
BibTeX 
@article{BUT76319,
  author="Alexandr {Meduna} and Petr {Zemek}",
  title="Workspace Theorems for Regular-Controlled Grammars",
  journal="Theoretical Computer Science",
  year="2011",
  volume="412",
  number="35",
  pages="4604--4612",
  doi="10.1016/j.tcs.2011.04.042",
  issn="0304-3975",
  url="http://www.sciencedirect.com/science/article/pii/S0304397511003513"
}
Nahoru