|
|
Parallel Multigenerative Cocke-Younger-Kasami-Based Parsing
Sopuch, Zbyněk ; Burgetová, Ivana (referee) ; Meduna, Alexandr (advisor)
We deal with text processing, pattern matching and syntax analysis every day, and new areas emerging. We can consider programming languages, communication protocols or a simple text as well-know examples. Therefore, we need new effective methods which fit into these areas. In this work, we explore the topics of parallel grammars, E0L-systems and multigenerative grammar systems. The goal is to improve the Cocke-Younger-Kasami algorithm and present a stronger algorithm of analysis.
|
|
| |
|
|
Parsing Based on Deep Pushdown Automata Systems
Šoustar, Jakub ; Kocman, Radim (referee) ; Meduna, Alexandr (advisor)
This thesis investigates deep pushdown automata and introduces their modification called controlled deep pushdown automata. Distributed deep pushdown automata systems and parallel communicating deep pushdown automata systems are described. Their accepting power and properties are investigated and several variants are introduced. This thesis proves that the accepting power of one such variant of parallel communicating deep pushdown automata systems is equal to the accepting power of Turing machines. A method for syntactical analysis based on the previously introduced automata systems is described.
|
|
|
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.
|
|
|
Parsing for ET0L Systems
Kožár, Tomáš ; Klobučníková, Dominika (referee) ; Meduna, Alexandr (advisor)
This thesis focuses on deciding the membership of strings in languages generated by ET0L systems. It is achieved by designing two algorithms. The first one is a modification of the existing algorithm Cocke-Younger-Kasami for syntax analysis of context-free grammars in Chomsky normal form. This modification takes into account different properties of ET0L systems compared to context-free grammars. Specifically, the parallel application of production rules and multiple tables of these production rules. Also, used normal form is different from Chomsky normal form since CNF is unfit for ET0L systems. The second designed algorithm works in a top-down manner and gradually generates all valid strings. The resulting algorithms are tested, demonstrated, and fully functional. The contributions of this thesis are two new algorithms for syntax analysis of ET0L systems.
|
|
|
Machine Understanding for Text Messages Used in Aviation
Lieskovský, Pavol ; Rajnoha, Martin (referee) ; Povoda, Lukáš (advisor)
This work deals with problems of NOTAM in text format, which is used in aeronautics. It documents the difference between text and digital format of NOTAM, special types of NOTAM messages and items from which the NOTAM consist of. It describes syntax and the functions of program, which was made within the frame of this thesis. The program is fully capable of correct parsing and processing of the NOTAM. The program can display each area of processed NOTAM messages in map and also provides detection of collision between these areas and flight plan
|
|
|
Parsing Based on Scattered Context Grammars
Horníček, Ondřej ; Solár, Peter (referee) ; Zámečníková, Eva (advisor)
This work deals with new possibilities in parsing based on advanced formal models, specifically using scattered context grammars in syntactic analysis. Context-sensitive language was created for comparing different methods of syntactic analysis, where these grammars are used. In conclusion is discussed possible use in practise, paralell parsing, pros and cons and further investigation.
|
|
|
New Versions of Automata and Grammar Systems
Lichota, Lukáš ; Kocman, Radim (referee) ; Meduna, Alexandr (advisor)
This work deals with the modification of classical grammar systems with context-free base and defines new, modified linear grammar systems with linear grammar base. Also it deals with modification in automata systems, where each automaton is generative as strong as linear grammar, which is satisfied with the usage of one-turn push-down automata. This thesis also contains view on program realisation of theoretical models, which were described in theoretical part and introduces two programs for syntax analysis built based on it.
|
|
|
Parsing Based on Modified Pushdown Automata
Pluháček, David ; Lukáš, Roman (referee) ; Meduna, Alexandr (advisor)
The thesis introduces new models for formal languages, the m-limited state grammar and the deep pushdown automaton. Their basic definitions are presented, so is their mutual equivalence and the characteristics of the language family they describe. Following, a parsing method based on these models is presented. The method is an extension of a similar method used for context-free languages, the table driven parsing. The final part of the thesis describes the implementation of a parser based on the method.
|
|
|
Parsing Based on State Grammars
Novotný, Miroslav ; Kocman, Radim (referee) ; Meduna, Alexandr (advisor)
This thesis's main focus is parsing, based on state grammars. The goal is to create a program, that will be able to load the grammar from input file. Based on a loaded grammar, the program will create an LL table and parse an input file using this table. The next goal is to study properties of parsing, based on state grammars, while using a created program as a stand point. Part of the testing will also be grammar structures which are not context-free.
|
guest ::
