Detail publikace

On the Generation of Sentences with Their Parses by Propagating Regular-Controlled Grammars

MEDUNA Alexander a ZEMEK Petr. On the Generation of Sentences with Their Parses by Propagating Regular-Controlled Grammars. Theoretical Computer Science, roč. 477, č. 1, 2013, s. 67-75. ISSN 0304-3975. Dostupné z: http://www.sciencedirect.com/science/article/pii/S0304397513000066
Název česky
O generování vět následovaných jejich rozbory propagujícími gramatikami řízenými 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

formální jazyky, bezkontextové gramatiky, regulárně řízené derivace, generování vět s jejich rozbory

Abstrakt

Tento článek vysvětluje, jak transformovat každou regulárně řízenou bezkontextovou gramatiku s kontrolou na výskyt G na regulárně řízenou bezkontextovou gramatiku s kontrolou na výskyt a bez vymazávacích pravidel G', jejíž jazyk L(G') obsahuje věty ve tvaru wz, kde w je z L(G) a z je rozbor w v G'. Tudíž, článek ukazuje, že pro každý rekurzivně spočetný jazyk K existuje regulárně řízená bezkontextová gramatika s kontrolou na výskyt a bez vymazávacích pravidel G' s jazykem L(G'), který obsahuje věty výše uvedeného tvary, ze kterého získáme K tak, že odstraníme všechna pravidla v L(G'). Článek navíc dokazuje analogické výsledky pro tyto gramatiky (a) bez kontroly na výskyt a (b) provádějící nejlevější derivace. V závěru jsou zmíněny některé důsledky dokázaných výsledků.

Rok
2013
Strany
67-75
Časopis
Theoretical Computer Science, roč. 477, č. 1, ISSN 0304-3975
Vydavatel
Elsevier Science
DOI
10.1016/j.tcs.2012.12.040
BibTeX 
@ARTICLE{FITPUB9715,
   author = "Alexander Meduna and Petr Zemek",
   title = "On the Generation of Sentences with Their Parses by Propagating Regular-Controlled Grammars",
   pages = "67--75",
   journal = "Theoretical Computer Science",
   volume = 477,
   number = 1,
   year = 2013,
   ISSN = "0304-3975",
   doi = "10.1016/j.tcs.2012.12.040",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/9715"
}
Nahoru