Detail publikace

One-Sided Random Context Grammars with Leftmost Derivations

MEDUNA Alexander a ZEMEK Petr. One-Sided Random Context Grammars with Leftmost Derivations. LNCS Festschrift Series: Languages Alive - Essays Dedicated to Jürgen Dassow on the Occasion of His 65th Birthday. Berlin-Heidelberg: Springer Verlag, 2012, s. 160-173. ISBN 978-3-642-31643-2. Dostupné z: https://www.scopus.com/record/display.uri?eid=2-s2.0-84867018824&origin=resultslist
Název česky
Jednostranné gramatiky s nahodilým kontextem s levými derivacemi
Typ
kapitola v knize
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, ří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, DE
DOI
10.1007/978-3-642-31644-9_11
EID Scopus
2-s2.0-84867018824
BibTeX 
@INBOOK{FITPUB9717,
   author = "Alexander Meduna and Petr Zemek",
   title = "One-Sided Random Context Grammars with Leftmost Derivations",
   pages = "160--173",
   booktitle = "LNCS Festschrift Series: Languages Alive - Essays Dedicated to J{\"{u}}rgen Dassow on the Occasion of His 65th Birthday",
   year = 2012,
   location = "Berlin-Heidelberg, DE",
   publisher = "Springer Verlag",
   ISBN = "978-3-642-31643-2",
   doi = "10.1007/978-3-642-31644-9\_11",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/9717"
}
Nahoru