Prof. RNDr. Alexander Meduna, CSc.

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
Jazyk publikace:angličtina
Název publikace:One-Sided Random Context Grammars with Leftmost Derivations
Název (cs):Jednostranné gramatiky s nahodilým kontextem s levými derivacemi
Strany:160-173
Kniha:LNCS Festschrift Series: Languages Alive - Essays Dedicated to Jürgen Dassow on the Occasion of His 65th Birthday
Místo vydání:Berlin-Heidelberg, DE
Rok:2012
URL:https://www.scopus.com/record/display.uri?eid=2-s2.0-84867018824&origin=resultslist
ISBN:978-3-642-31643-2
DOI:10.1007/978-3-642-31644-9_11
Vydavatel:Springer Verlag
Klíčová slova
formální jazyky, řízené přepisování, jednostranné gramatiky s nahodilým kontextem, levé derivace, generativní síla
Anotace
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.
BibTeX:
@INBOOK{
   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 = {http://www.fit.vutbr.cz/research/view_pub.php.cs?id=9717}
}

Vaše IPv4 adresa: 34.236.190.216
Přepnout na https