Detail publikace

One-Sided Random Context Grammars with Leftmost Derivations

MEDUNA, A.; ZEMEK, P. One-Sided Random Context Grammars with Leftmost Derivations. In LNCS Festschrift Series: Languages Alive - Essays Dedicated to Jürgen Dassow on the Occasion of His 65th Birthday. Berlin-Heidelberg: Springer Verlag, 2012. p. 160-173. ISBN: 978-3-642-31643-2.
Název česky
Jednostranné gramatiky s nahodilým kontextem s levými derivacemi
Typ
kapitola v knize
Jazyk
anglicky
Autoři
Meduna Alexandr, prof. RNDr., CSc. (UIFS)
Zemek Petr, Ing., Ph.D.
URL
Klíčová slova

formální jazyky, řízené přepisování, jednostranné gramatiky s nahodilým kontextem, levé derivace, generativní síla

Abstrakt

V článku je studována generativní síla jednostranných gramatik s nahodilým kontextem pracujícími levým způsobem. Analogicky se třemi dobře známými typy levých derivací v řízených gramatikách zavádíme tři typy levých derivací do jednostranných gramatik s nahodilým kontextem a dokazujeme následující tři výsledky. (I) Jednostranné gramatiky s levými derivacemi typu 1 charakterizují třídu bezkontextových jazyků. (II) Jednostranné gramatiky s levými derivacemi typu 2 a 3 charakterizují třídu rekurzivně spočetných jazyků. (III) Jednostranné gramatiky bez vymazávacích pravidel s levými derivacemi typu 2 a 3 charakterizují třídu kontextových jazyků. V závěru je porovnána síla jednostranných gramatik s nahodilým kontextem a gramatik s nahodilým kontextem, obě pracující levým způsobem.

Rok
2012
Strany
160–173
Kniha
LNCS Festschrift Series: Languages Alive - Essays Dedicated to Jürgen Dassow on the Occasion of His 65th Birthday
ISBN
978-3-642-31643-2
Vydavatel
Springer Verlag
Místo
Berlin-Heidelberg
DOI
10.1007/978-3-642-31644-9_11
EID Scopus
2-s2.0-84867018824
BibTeX 
@inbook{BUT96922,
  author="Alexandr {Meduna} and Petr {Zemek}",
  title="One-Sided Random Context Grammars with Leftmost Derivations",
  booktitle="LNCS Festschrift Series: Languages Alive - Essays Dedicated to Jürgen Dassow on the Occasion of His 65th Birthday",
  year="2012",
  publisher="Springer Verlag",
  address="Berlin-Heidelberg",
  pages="160--173",
  doi="10.1007/978-3-642-31644-9\{_}11",
  isbn="978-3-642-31643-2",
  url="https://www.scopus.com/record/display.uri?eid=2-s2.0-84867018824&origin=resultslist"
}
Nahoru