|
|
New Parallel and Regulated Automata and Grammars
Kučera, Jiří ; Průša, Daniel (referee) ; Sawa, Zdeněk (referee) ; Meduna, Alexandr (advisor)
Tato práce zkoumá a zavádí čtyři nové jazykové modely se zaměřením na regulované a paralelní verze automatů a gramatik. První z modelů, stavově synchronizované systémy automatů , zavádí systémy složené z konečného počtu zásobníkových automatů jejichž činnost je řízena slovy z řídícího jazyka nad množinou stavů. Druhý model, neomezené hluboké zásobníkové automaty , je variantou hlubokých zásobníkových automatů z nichž bylo sejmuto omezení kladené na hloubku expanze na zásobníku. Třetí model, skákající čisté gramatiky , zavádí skákající gramatiky bez neterminálních symbolů. Poslední model, k#$-přepisující systémy , rozšiřuje #-přepisující systémy o přídavnou zásobníkovou paměť. Text této práce je členěn do tří částí. První část uvádí motivaci k zavedení studovaných jazykových modelů a zasazuje je do kontextu souvisejících oblastí teorie formálních jazyků. Je zde také uveden přehled o celkové organizaci práce, základních pojmů teorie formálních jazyků a současných poznatků souvisejících s předmětem výzkumu. Druhá část tvoří jádro této práce. Jsou v ní formálně definovány všechny nově zavedené jazykové modely a studována jejich vyjadřovací síla. Poslední část uzavírá tuto práci souhrnem získaných teoretických výsledků společně se souvisejícími otevřenými problémy a nastiňuje cesty dalšího výzkumu spolu s výhledy na možná využití.
|
|
| |
|
|
New Versions of Translation Automata
Baláž, Miroslav ; Klobučníková, Dominika (referee) ; Meduna, Alexandr (advisor)
This thesis does research on new version of translation automata. It takes closer look at existing pushdown transcuders and regulated grammar. Combining these two concepts together which creates new regulated pushdown transcuder as a new form of translation automata. Examine computational power of regulated grammar and tests its usage combined with transcuder and test usablity of this new defined regulated transcuder in implementation for translating input source code.
|
|
|
Parsing Based on Automata with Deep Pushdowns
Rusek, David ; Kocman, Radim (referee) ; Meduna, Alexandr (advisor)
This paper addresses the issue of design and implementation of syntactic analysis based on the context sensitive languages, respectively, grammars that contains constructs, which isn't possible to analyze with the help of the standard parsers based on the context free grammars. More specifically, this paper deals with the possibility of adding context sensitive support to the classic LL-analysis by replacing the standard pushdown automata (PDA) with deep pushdown automata (DP), which were introduced and published by prof. Alexander Meduna.
|
|
|
Automata with a Limited Number of Pure Pushdowns
Soukup, Ondřej ; Zemek, Petr (referee) ; Meduna, Alexandr (advisor)
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.
|
|
|
Parsing Based on Deep Pushdown Automata
Senko, Jozef ; Vrábel, Lukáš (referee) ; Solár, Peter (advisor)
This thesis is concerning with syntax analysis based on deep pushdown automata. In theoretical part are defined themselves deep pushdown automata, all the necessary theoretical concepts and then is discussed the implementation of these deep pushdown automata embedded in the educational program for students.
|
|
|
Parsing Based on Regulated Automata
Genčúrová, Ľubica ; Martiško, Jakub (referee) ; Meduna, Alexandr (advisor)
This work deals with the design, applicability and the implementation of parsing methods based on pushdown automata that regulate the use of their rules by linear control languages. These automata are more powerful than ordinary automata and they are as powerful as Turing machine. The pushdown automata regulated by linear control languages characterize the family of recursively enumerable languages.
|
|
|
Visualization of Finite Automata, Pushdown Automata and Turing Machines Work
Syrový, Ondřej ; Láník, Aleš (referee) ; Zuzaňák, Jiří (advisor)
This bachelor`s thesis is focusing on concept and development of computer application for demonstration of finite automata, pushdown automata and Turing machines work. Theoretic volume of this work deals with theories of formal languages and grammars and automata theory. Created program allows to load deterministic and nondeterministic automata variants from the text file, their graphic representation by state diagram and stepping their calculation process.
|
|
|
Pushdown Systems and Parsing Based on Them
Křesťan, Zdeněk ; Kocman, Radim (referee) ; Meduna, Alexandr (advisor)
This thesis focuses on the use of deep pushdown automaton in parsing . This method overcomes the power of traditional context - free grammars . The predictive parsing algorithm, driven by LL table, is modified by the use of deep pushdown automaton . The modifications extended LL tables by adding depth , in order for tables to collaborate with the deep pushdown automaton .
|
|
|
Parsing Based on State Grammars
Svatý, Lukáš ; Vrábel, Lukáš (referee) ; Solár, Peter (advisor)
Syntax-directed translation based on state grammars is introduced in this bachelor's thesis. Theoretical section of this thesis is focused on the introduction of theoretical models that are necessary for understanding syntax analysis based on state grammars. The most important theoretical formal models in this thesis include deep pushdown transducer and translation grammar based on state grammar, which can be used in syntax analysis. Practical section of this thesis is focused on bottom-up syntax analysis using state grammar and its implementation.
|
guest ::
