|
|
Predictive Parsing with Deep Pushdowns
Viktorin, Jiří ; Blatný, Petr (referee) ; Meduna, Alexandr (advisor)
This paper introduces a generalization of classical pushdown automata-deep pushdown automata. Deep pushdown automata expand a pushdown symbol in a depth defined by a rule. Deep pushdown expands a non-terminal in the deep defined in the rule and this non-terminal need not be on the top of pushdown.
|
|
|
The Pushdown Automaton Simulator
Graizely, Martin ; Blatný, Petr (referee) ; Bidlo, Radek (advisor)
Visualization often helps with the understanding and allows for a quicker grasp of the problem. This work is aimed on implementation of pushdown automaton simulator. The purpose of the application is to ease understanding of such abstract machine and its abilities, by providing visual design and possibility of algorithm's interactive animation.
|
|
|
Conversions between CF Grammars and Pushdown Automata
Makovský, Benjamin ; Goldefus, Filip (referee) ; Masopust, Tomáš (advisor)
This work suggests and solves the implementation of the transformation of context-free grammars and the conversions between context-free grammars and pushdown automata. It makes acquainted with the models used in modern theory of formal languages. In the work are indicated all algorithms necessary for transformations and mutual conversions between context-free grammars and pushdown automata. Proposed is an object representing the grammar and the automaton in the programme. Described is the assigning of definitions of grammar and of the automaton, the solution of drawing the automaton on the screen and the creation of graphical user interface of the application. The resulting programme is developed as Jawa applet which is available on public internet pages www.convertcfg.php5.cz.
|
|
|
Semi-Parallel Deep Pushdown Automata
Ševčík, Miroslav ; Zámečníková, Eva (referee) ; Meduna, Alexandr (advisor)
This work introduces semi-parallel deep pushdown automata as an extension of sequential deep pushdown automata. Unlike the sequential automaton, a semi-parallel one is able to make expansions of n nonterminal symbols on the pushdown top simultaneously. These automata, same as sequential deep pushdown automata, define the family of languages generated by n-limited state grammars. The advantage of semi-parallel deep pushdown automata lies in higher speed. This work also describes the implementation of an aplication that simulates operation of these automata.
|
|
|
Parsing Based on Multigeneration
Kyjovská, Linda ; Přikryl, Zdeněk (referee) ; Lukáš, Roman (advisor)
This work deals with syntax analysis problems based on multi-generation. The basic idea is to create computer program, which transforms one input string to n -1 output strings. An Input of this program is some plain text file created by user, which contains n grammar rules. Just one grammar from the input file is marked as an input grammar and others n -1 grammars are output grammars. This program creates list of used input grammar rules for an input string and uses corresponding output grammar rules for the creation of n -1 output strings. The program is written in C++ and Bison
|
|
|
Systems of Formal Models with Applications
Čermák, Martin ; Lukáš, Roman (referee) ; Meduna, Alexandr (advisor)
This paper introduces and discusses automata systems as a new way for formal languages processing. In the text there are four models described. The first model works on sequential mode. At one computation step only one of components works. The second one works on semi-parallel mode. At the one computation step either one or all the components of the automata system work. In the last two models each component of the automata system has its own input string. The computation step of each component is influenced by their states, or used rules. The state, or used rule of the components of automata system can block or unblock some or all automata of the system.
|
|
|
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.
|
|
|
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.
|
|
| |
|
|
New Versions of Pushdown Automata
Genčúrová, Ľubica ; Kocman, Radim (referee) ; Meduna, Alexandr (advisor)
This thesis investigates multi pushdown automata and introduces their new modifications based on deep pushdown. The first modification is Input driven multi deep pushdown automata, which has several deep pushdown lists and the current input symbol determines whether the automaton performs a push operation, a pop operation, an expansion operation or does not touch the stack. The second introduced modification is Regulated pushdown automata by deep pushdown. In addition to ordinary pushdowns, this version contains deep pushdown, which is used to generate the control language. This thesis proves, that the acceptance power of the described variants is equal to the accepting power of Turing machines. This thesis also contains view on program realisation of theoretical models, which were described in the theoretical part and introduces a library for the syntax analysis, which is based on it.
|
guest ::
