Název: Omezení větných forem gramatik s rozptýleným kontextem
Překlad názvu: A Restriction of Sentetial Forms of of Scattered Context Grammars
Autoři: Šimáček, Jiří ; Masopust, Tomáš (oponent) ; Meduna, Alexandr (vedoucí práce)
Typ dokumentu: Diplomové práce
Rok: 2008
Jazyk: cze
Nakladatel: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstrakt: [cze] [eng]
Tato práce zavádí pojem zobecněných gramatik s rozptýleným kontextem, které se od tradičních liší tím, že levé strany pravidel mohou obecně obsahovat řetězec neterminálních symbolů namísto jediného neterminálu. Dále jsou studovány dva typy omezení při větné derivaci v těchto gramatikách. Nechť k je konstanta. První omezení požaduje, aby přepsání všech symbolů nastalo mezi prvními k symboly v prvním souvislém bloku neterminálů ve větné formě v každém derivačním kroku. Druhé omezení definuje derivaci pouze nad větnými formami, které obsahují nejvýše k výskytů neterminálů. Jako hlavní výsledek práce demonstruje, že oba typy omezení snižují vyjadřovací sílu na úroveň bezkontextových gramatik. This work introduces and discusses generalized scattered context grammars that are based upon sequences of productions whose left-hand sides are formed by nonterminal strings, not just single nonterminals. It places two restrictions on the derivations in these grammars. More specifically, let k be a constant. The first restriction requires that rewriting all symbols occurs within the first k symbols of the first continuous block of nonterminals in the sentential form during every derivation step. The other restriction defines the derivations over sentential forms containing no more than k occurrences of nonterminals. As its main result, the thesis demonstrates that both restrictions decrease the generative power of these grammars to the power of context-free grammars.
Klíčová slova: gramatiky s rozptýleným kontextem; omezení větné derivace; vyjadřovací síla; zobecnění gramatik; derivation restriction; generative power; grammatical generalization; scattered context grammars

Instituce: Vysoké učení technické v Brně (web)
Informace o dostupnosti dokumentu: Plný text je dostupný v Digitální knihovně VUT.
Původní záznam: http://hdl.handle.net/11012/53163

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-235920


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Vysoké učení technické v Brně
Vysokoškolské kvalifikační práce > Diplomové práce