Článek v časopise

 
Meduna, A., Zemek, P.: Workspace Theorems for Regular-Controlled Grammars, In: Theoretical Computer Science, roč. 412, č. 35, 2011, Paris, FR, s. 4604-4612, ISSN 0304-3975
Jazyk publikace:angličtina
Název publikace:Workspace Theorems for Regular-Controlled Grammars
Název (cs):Workspace věty pro gramatiky řízené regulárním jazykem
Strany:4604-4612
Místo vydání:FR
Rok:2011
URL:http://www.sciencedirect.com/science/article/pii/S0304397511003513
Časopis:Theoretical Computer Science, roč. 412, č. 35, Paris, FR
ISSN:0304-3975
URL:http://www.sciencedirect.com/science/article/pii/S0304397511003513 [HTML]
Klíčová slova
Bezkontextové gramatiky řízené regulárním jazykem, workspace podmínky, odstraňování vymazávacích pravidel
Anotace
Č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ů.

BibTeX:
@ARTICLE{
   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},
   language = {english},
   url = {http://www.fit.vutbr.cz/research/view_pub.php?id=9583}
}