Název: Deep Pushdown Automata and Their Restricted Versions
Překlad názvu: Deep Pushdown Automata and Their Restricted Versions
Autoři: Charvát, Lucie ; Kučera, Jiří (oponent) ; Meduna, Alexandr (vedoucí práce)
Typ dokumentu: Diplomové práce
Rok: 2017
Jazyk: eng
Nakladatel: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstrakt: [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.
Klíčová slova: Deep pushdown automata; pushdown alphabet reduction; Hluboké zasobníkové automaty; redukce zásobníkové abecedy

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

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-363840


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Vysoké učení technické v Brně
Vysokoškolské kvalifikační práce > Diplomové práce