Original title: Syntaktická analýza založená na systémech hlubokých zásobníkových automatů
Translated title: Parsing Based on Deep Pushdown Automata Systems
Authors: Šoustar, Jakub ; Kocman, Radim (referee) ; Meduna, Alexandr (advisor)
Document type: Master’s theses
Year: 2017
Language: cze
Publisher: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract: [cze] [eng]
Tato práce se zabývá hlubokými zásobníkovými automaty a zavádí jejich modifikaci nazvanou řízený hluboký zásobníkový automat. Dále jsou v této práci představeny distribuované systémy hlubokých zásobníkových automatů a paralelně komunikující systémy řízených hlubokých zásobníkových automatů. Jsou zkoumány vlastnosti a vyjadřovací síla těchto automatových systémů a je zavedeno několik variant těchto systémů. Pro jednu z variant paralelně komunikujících systémů je dokázáno, že disponuje stejnou vyjadřovací silou, jakou mají Turingovy stroje. Na základě těchto automatových systémů je zavedena metoda syntaktické analýzy. This thesis investigates deep pushdown automata and introduces their modification called controlled deep pushdown automata. Distributed deep pushdown automata systems and parallel communicating deep pushdown automata systems are described. Their accepting power and properties are investigated and several variants are introduced. This thesis proves that the accepting power of one such variant of parallel communicating deep pushdown automata systems is equal to the accepting power of Turing machines. A method for syntactical analysis based on the previously introduced automata systems is described.
Keywords: deep pushdown automata; determinism; distributed automata systems; parallel communicating automata systems; parsing; determinismus; distribuované systémy automatů; hluboké zásobníkové automaty; paralelně komunikující systémy automatů; syntaktická analýza

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

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


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