|
|
Omezení větných forem gramatik s rozptýleným kontextem
Šimáček, Jiří ; Masopust, Tomáš (oponent) ; Meduna, Alexandr (vedoucí práce)
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.
|
|
|
New Versions of Classical Automata and Grammars
Soukup, Ondřej ; Solár, Peter (oponent) ; Meduna, Alexandr (vedoucí práce)
This master's thesis investigates new versions of automata and grammars and is thus divided into two parts. First part defines and studies pure multi-pushdown automata and additionally introduces total orders above their pushdowns or pushdown symbols. Present work proves, defined restrictions decrease accepting power of these automata. In the second part, new modes of scattered context derivations are defined and described, which generalize the relation of direct derivation. It is proved, these modes do not decrease the generation power of scattered context grammars.
|
|
|
Turingovy stroje bez návratu na pásce
Surovič, Marek ; Vrábel, Lukáš (oponent) ; Meduna, Alexandr (vedoucí práce)
Tato práce zavádí omezenou variantu Turingových strojů, které se nemohou pohybovat doleva, tedy se vracet na pásce. Ostatní vlastnosti Turingových strojů (například potenciálně nekonečná páska a schopnost přepisovat symboly na pásce) jsou zachovány. Zavedením tohoto omezení limitujeme vyjadřovací sílu Turingových strojů do té míry, ľe Turingovy stroje bez návratu na pásce jsou ekvivalentní s konečnými automaty a lze je na konečný automat transformovat. Dále je představen a detailně popsán algoritmus, který realizuje tuto transformaci.
|
|
|
New Versions of Classical Automata and Grammars
Soukup, Ondřej ; Solár, Peter (oponent) ; Meduna, Alexandr (vedoucí práce)
This master's thesis investigates new versions of automata and grammars and is thus divided into two parts. First part defines and studies pure multi-pushdown automata and additionally introduces total orders above their pushdowns or pushdown symbols. Present work proves, defined restrictions decrease accepting power of these automata. In the second part, new modes of scattered context derivations are defined and described, which generalize the relation of direct derivation. It is proved, these modes do not decrease the generation power of scattered context grammars.
|
|
|
Turingovy stroje bez návratu na pásce
Surovič, Marek ; Vrábel, Lukáš (oponent) ; Meduna, Alexandr (vedoucí práce)
Tato práce zavádí omezenou variantu Turingových strojů, které se nemohou pohybovat doleva, tedy se vracet na pásce. Ostatní vlastnosti Turingových strojů (například potenciálně nekonečná páska a schopnost přepisovat symboly na pásce) jsou zachovány. Zavedením tohoto omezení limitujeme vyjadřovací sílu Turingových strojů do té míry, ľe Turingovy stroje bez návratu na pásce jsou ekvivalentní s konečnými automaty a lze je na konečný automat transformovat. Dále je představen a detailně popsán algoritmus, který realizuje tuto transformaci.
|
|
|
Omezení větných forem gramatik s rozptýleným kontextem
Šimáček, Jiří ; Masopust, Tomáš (oponent) ; Meduna, Alexandr (vedoucí práce)
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.
|
host ::
RSS.