Název:
Nové verze zásobníkových automatů
Překlad názvu:
New Versions of Pushdown Automata
Autoři:
Genčúrová, Ľubica ; Kocman, Radim (oponent) ; Meduna, Alexandr (vedoucí práce) Typ dokumentu: Diplomové práce
Rok:
2019
Jazyk:
cze
Nakladatel: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstrakt: [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.
Klíčová slova:
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; 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
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/180328