Original title: Nové verze zásobníkových automatů
Translated title: New Versions of Pushdown Automata
Authors: Genčúrová, Ľubica ; Kocman, Radim (referee) ; Meduna, Alexandr (advisor)
Document type: Master’s theses
Year: 2019
Language: cze
Publisher: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract: [cze] [eng]
Táto diplomová práca sa zaoberá verziami viac-zásobníkových automatov založených na hlbokých zásobníkoch. Zavádza novú modifikáciu Vstupom riadený hlboký viac-zásobníkový automat, ktorý pozostáva z dvoch a viac hlbokých zásobníkov a aktuálny vstupný symbol určuje, či automat vykonáva operáciu push, operáciu pop alebo operáciu rozšírenia, poprípade obsah zásobníka nezmení. Druhou zavedenou variantou je Zásobníkový automat regulovaný hlbokým zásobníkom. Okrem bežného zásobníka obsahuje táto verzia aj hlboký zásobník, na ktorom je generovaný riadiaci jazyk. Táto práca dokazuje, že vyjadrovacia sila nových modifikácií automatov sa rovná vyjadrovacej sile Turingových strojov. Práca transformuje teoretické modely navrhnutých automatov na reálnu implementáciu a ponúka knižnicu implementujúcu syntaktickú analýzu založenú na týchto modeloch. This thesis investigates multi pushdown automata and introduces their   new modifications based on deep pushdown.  The first modification is Input driven multi deep pushdown automata, which has several deep pushdown lists and the current input symbol determines whether the automaton performs a push operation, a pop operation, an expansion operation or does not touch the stack. The second introduced modification is Regulated pushdown automata by deep pushdown. In addition to ordinary pushdowns, this version contains deep pushdown, which is used to generate the control language. This thesis proves, that the acceptance power of the described variants  is equal to the accepting power of Turing machines.  This thesis also contains view on program realisation of theoretical models, which were described in the theoretical part and introduces a library for the syntax analysis, which is based on it.
Keywords: deep pushdown expansions; deep-pushdown automata; input driven multi deep-pushdown automata; modified pushdown automata; multi pushdown automata; one-turn pushdown automata; pushdown automata; regulated pushdown automata by deep pushdown; syntax analysis; two-pushdown automaton; dvoj-zásobníkový automat; expanzie v hĺbke zásobníka; hlboký viac-zásobníkový automat riadený vstupom; hlboký zásobníkový automat; jedno-otáčkový zásobníkový automat; modifikované zásobníkové automaty; syntaktická analýza; viac-zásobníkový automat; zásobníkový automat; zásobníkový automat regulovaný hlbokým zásobníkom

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/180328

Permalink: http://www.nusl.cz/ntk/nusl-570959


The record appears in these collections:
Universities and colleges > Public universities > Brno University of Technology
Academic theses (ETDs) > Master’s theses