Název:
New Versions of Classical Automata and Grammars
Překlad názvu:
New Versions of Classical Automata and Grammars
Autoři:
Soukup, Ondřej ; Solár, Peter (oponent) ; Meduna, Alexandr (vedoucí práce) Typ dokumentu: Diplomové práce
Rok:
2013
Jazyk:
eng
Nakladatel: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstrakt: [eng][cze]
Tato diplomová práce se zabývá zkoumáním nových verzí automatů a gramatik a je proto rozdělena do dvou částí. První část definuje a studuje čisté více zásobníkové automaty a navíc zavádí úplná uspořádání nad jejich zásobníky nebo zásobníkovými symboly. Práce dokazuje, že zavedená omezení snižují vyjadřovací sílu automatů. Ve druhé části práce jsou definovány a popsány nové derivační módy gramatik s rozptýleným kontextem, které zobecňují relaci přímé derivace. Je dokázáno, že jejich použití nesnižuje vyjadřovací sílu gramatik.
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.
Klíčová slova:
accepting power; derivation modes; Pure multi-pushdown automata; scattered context grammars; total orders; derivační módy; gramatiky s rozptýleným kontextem; vyjadřovací síla; úplná uspořádání; Čisté vícezásobníkové automaty
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/61786