|
|
Simulace a protiřetězce pro efektivní práci s konečnými automaty
Holík, Lukáš ; Černá, Ivana (referee) ; Jančar, Petr (referee) ; Vojnar, Tomáš (advisor)
Cílem této práce je vývoj technik umožňujících praktické využití nedeterministických konečných automatů, zejména nedeterministických stromových automatů. Jde zvláště o techniky pro redukci velikosti a testování jazykové inkluze, jež hrají zásadní roli v mnoha oblastech aplikace konečných automatů. V oblasti redukce velikosti vycházíme z dobře známých metod pro slovní automaty které jsou založeny na relacích simulace. Navrhli jsme efektivní algoritmy pro výpočet stromových variant simulačních relací a identifikovali jsme nový typ relace založený na kombinaci takzvaných horních a dolních simulací nad stromovými automaty. Tyto kombinované relace jsou zvláště vhodné pro redukci velikosti automatů slučováním stavů. Navržený princip kombinace relací simulace je relevantní i pro slovní automaty. Náš přínos v oblasti testování jazykové inkluze je dvojí. Nejprve jsme zobecnili na stromové automaty takzvané protiřetězcové algoritmy, které byly původně navrženy pro slovními automaty. Dále se nám podařilo použitím simulačních relací výrazně zefektivnit protiřetězcové algoritmy pro testování jazykové inkluze jak pro slovní, tak pro stromové automaty. Relevanci našich technik pro praxi jsme demonstrovali jejich nasazením v rámci regulárního stromového model checkingu, což je verifikační metoda založená na stromových automatech. Použití našich algoritmů zde vedlo k výraznému zrychlení a zvětšení škálovatelnosti celé metody. Základní myšlenky našich algoritmů pro redukci velikosti automatů a testování jazykové inkluze jsou aplikovatelné i na jiné typy automatů. Příkladem jsou naše redukční techniky pro alternující Büchiho automaty prezentované v poslední části práce.
|
|
| |
|
| |
|
|
Languages, Grammars and Machines
Mocková, Ľubica ; Zimmerová, Barbora (referee) ; Bobalová, Martina (advisor)
My thesis is a brief synopsis of the basic types of formal languages, grammars and machines, which are a part of theoretical computer science. My thesis contains the survey of the theory related to the given topic and problems related to the theoretical part of my thesis. This work is to be used as a study material for the students of the Faculty of Business and Management for the subject of Discrete Mathematics. It can also be helpful for the students of other universities and faculties whose curricula contain theory of grammars and machines.
|
|
|
Symbolic Representation of Finite Automata
Chromečka, Jiří ; Vojnar, Tomáš (referee) ; Lengál, Ondřej (advisor)
In formal analysis we often encounter finite automata with a~large amount of states over large alphabets. Their explicit representation can result in a~state explosion and this problem can be solved by the use of symbolic representation that can manipulate a~whole set of states at once. The aim of this work is to extend the libVATA library to support such a~representation including algorithms for some operations on this representation. The presented text first deals with prerequisites necessary to undestand finite automata and binary decision diagrams used for their symbolic representation. Then it lists some existing libraries for work with finite automata. Next follows the core of this work, the~design of a~symbolic representation and operations on it, which are later implemented in the previously mentioned library. The test results proves that the symbolic representation is an interesting alternative to the explicit representation.
|
|
|
Simulation of Lazy Finite Automata
Vrábel, Lukáš ; Masařík, Karel (referee) ; Lukáš, Roman (advisor)
This bachelor's thesis introduces a formal model of the lazy finite state machine and implementation of application based on this model. The application demonstrates functionality of new model, and pros and cons of this approach. This model has advantage over existing models in easier definitions of transition rules.
|
|
|
Context-Dependent Scanner
Hatina, Peter ; Koutný, Jiří (referee) ; Čermák, Martin (advisor)
This paper is devoted to principles of a lexical analysis and to a means of context resolution of a lexeme type, depending on its source code position. The lexical analysis, process of a lexical analyzer creation and possible solution for context lexeme recognition, based on a multiple automata system, is described. Lexical analyzer functionality is extended to accept tokens in other languages code blocks.
|
|
|
Parallel Lexical Analyzer
Ježek, Lukáš ; Koutný, Jiří (referee) ; Čermák, Martin (advisor)
This bachelor thesis deals with generating a lexical analyzer which analyzes a file in parallel, i.e. by several threads at a time. The analyzer is generated on the basis of regular language and is represented by finite automaton with the necessary functions. The emphasis is placed on the parallel processing. The possibility of forward and back threads processing is discussed in this thesis. The method of the forward threads was decided to be used for implementation. The problems during implementation that lead to almost none of the desired speed-up of the analysis are discussed.
|
|
|
Demonstration Program of Convertion of Finite Automata
Štorek, Vojtěch ; Novotný, Tomáš (referee) ; Lukáš, Roman (advisor)
The main goal of practical part of this work is to create a program, which applies finite automata theory in practice and makes this theory easier to understand. Program is capable to easily create finite automata and make didactic demostration of basic theoretical knowledges such as coversion to special types of finite automata, function illustration or representation of finite automata in form of C language source code. In this technical report I will try to describe, how are individual key parts of the application implemented.
|
|
|
Multi-Word Term Extraction
Seitler, Andrej ; Schmidt, Marek (referee) ; Smrž, Pavel (advisor)
The main goal of project is to study the ways how to find multi-word expressions in the text and to create a program, that is searching for occurence of idiomas from input file in corpus. Program lay stress on searching rate. The output consists of idioma found in corpus, rate of occurence in text and sentences, where can be idioma found. Project also have a library, which is used as sentence splitter.
|
guest ::
