Original title: Deep Pushdown Automata and Their Restricted Versions
Translated title: Deep Pushdown Automata and Their Restricted Versions
Authors: Charvát, Lucie ; Kučera, Jiří (referee) ; Meduna, Alexandr (advisor)
Document type: Master’s theses
Year: 2017
Language: eng
Publisher: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract: [eng] [cze]
Pro přirozené číslo n, n-expandovatelné hluboké zasobníkové automaty vždy obsahují maximálně n výskytů nevstupních symbolů v jejich zásobníku v průběhu jakékoli kompilace. Jako hlavní výsledek, tato práce demonstruje, že tyto automaty mají stejnou vyjadřovací sílu jako automaty s #, nacházející pouze na dně zásobníku, a jediným dalším nevstupním symbolem. Z tohoto závěru vyplývá nekonečná hierarchie jazyků přijímaných těmito automaty. For a positive integer n, n-expandable deep pushdown automata always contain no more than n occurrences of non-input symbols in their pushdowns during any compilation. As its main result, the present thesis demonstrates that those automata are as powerful as the same automata with #, which always appears solely as the pushdown bottom, and a single pushdown non-input symbol. An infinite hierarchy of language families follows from this result.
Keywords: Hluboké zasobníkové automaty; redukce zásobníkové abecedy; Deep pushdown automata; pushdown alphabet reduction

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

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


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