Detail publikace

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

MEDUNA, A.; ZEMEK, P. On the Generation of Sentences with Their Parses by Propagating Regular-Controlled Grammars. Theoretical Computer Science, 2013, vol. 477, no. 1, p. 67-75. ISSN: 0304-3975.
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
anglicky
Autoři
Meduna Alexandr, prof. RNDr., CSc. (UIFS)
Zemek Petr, Ing., Ph.D.
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
DOI
10.1016/j.tcs.2012.12.040
BibTeX 
@article{BUT103400,
  author="Alexandr {Meduna} and Petr {Zemek}",
  title="On the Generation of Sentences with Their Parses by Propagating Regular-Controlled Grammars",
  journal="Theoretical Computer Science",
  year="2013",
  volume="477",
  number="1",
  pages="67--75",
  doi="10.1016/j.tcs.2012.12.040",
  issn="0304-3975",
  url="http://www.sciencedirect.com/science/article/pii/S0304397513000066"
}
Nahoru