Všechny publikace
| Meduna, A., Zemek, P.: 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, DE, Springer, 2012, s. 160-173, ISBN 978-3-642-31643-2 | | 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: | http://www.springerlink.com/content/mx44705255227153/ |
|---|
| ISBN: | 978-3-642-31643-2 |
|---|
| Vydavatel: | Springer Verlag |
|---|
| URL: | http://www.springerlink.com/content/mx44705255227153/ [HTML] |
|---|
| 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ürgen Dassow on the Occasion of His 65th Birthday},
year = {2012},
location = {Berlin-Heidelberg, DE},
publisher = {Springer Verlag},
ISBN = {978-3-642-31643-2},
language = {english},
url = {http://www.fit.vutbr.cz/research/view_pub.php?id=9717}
} |
|
Fakulta informačních technologií
![[dnssec]](/common/img/dnssec.png)