Original title: Automaty s ohraničeným počtem čistých zásobníků
Translated title: Automata with a Limited Number of Pure Pushdowns
Authors: Soukup, Ondřej ; Zemek, Petr (referee) ; Meduna, Alexandr (advisor)
Document type: Bachelor's theses
Year: 2011
Language: cze
Publisher: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract: [cze] [eng]
Zásobníkové automaty s omezeným počtem čistých zásobníků jsou specializací čistých zásobníkových automatů. Jejich síla je zkoumána především z pohledu kombinatoriky na slovech. V jazyku definovaném automatem je zaveden termín závislost, který označuje vztah mezi částmi řetězců jazyka. Je ukázáno, jak postupuje definovaný automat při zpracování závislostí. Dále je odvozen vztah mezi rozložením závislostí v jazyku a nutným počtem zásobníků automatu. Je definována nekonečná hierarchie jazyků korespondujících k automatům v závislosti na počtu jejich zásobníků. Nakonec je zkoumáno zařazení třídy jazyků definované zásobníkovými automaty s omezeným počtem čistých zásobníků do Chomského hierarchie jazyků, ovšem je zjištěno, že s Chomského hierarchií nekorespondují. Na základě výsledku je jako další vývoj navrhováno zkoumání možných úprav modelů. Pro demonstraci vlastností zkoumaných automatů je následně vytvořen simulační program. Pushdown automata with limited number of pure pushdowns are specialization of pure pushdown automata. Examination of their power is mainly focused on the view of combinatorics of words. In language defined by automata we introduce term of dependence, which denotes relation between parts of strings in language. It is shown, how the defined automata proceed on processing of dependencies. Then the relation between distribution of dependencies in language and required number of pushdowns is derived. Also is defined the infinite hierarchy of languages corresponding to automata in dependence on number of their pushdowns. At the end belonging of the class of languages defined by pushdown automata with limited number of pure pushdowns to Chomsky hierarchy of languages is studied, but it is discovered, that they do not correspond to Chomsky hierarchy. Based on this result it is proposed to study possible changes of models as a future development. Then the simulating program is created to illustrate features of examined automata.
Keywords: combinatorics of words; pure pushdowns; Pushdown automata; kombinatorika na slovech; Zásobníkové automaty; čisté zásobníky

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

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


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