Original title:
New Versions of Classical Automata and Grammars
Translated title:
New Versions of Classical Automata and Grammars
Authors:
Soukup, Ondřej ; Solár, Peter (referee) ; Meduna, Alexandr (advisor) Document type: Master’s theses
Year:
2013
Language:
eng Publisher:
Vysoké učení technické v Brně. Fakulta informačních technologií Abstract:
[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.
Keywords:
derivační módy; gramatiky s rozptýleným kontextem; vyjadřovací síla; úplná uspořádání; Čisté vícezásobníkové automaty; accepting power; derivation modes; Pure multi-pushdown automata; scattered context grammars; total orders
Institution: Brno University of Technology
(web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library. Original record: http://hdl.handle.net/11012/61786