|
|
Construction of the Generalized Finite Automaton
Šoka, Martin ; Košař, Vlastimil (referee) ; Kaštil, Jan (advisor)
The thesis deals with the creation of an algorithm for the construction of the generalized finite automaton. This automaton differs from the conventional finite automaton by the fact that its transitions are defined by words, therefore it is possible to reduce the number of states of the generalized finite automaton. The introduction includes definitions of terms used later in the thesis. In the next chapters I describe the algorithm itself, including the comprehensive analysis of the heuristics for finding a maximal acyclic subgraph in the graph of the automaton. It also describes implementation of the algorithm and experimentation with automatons created by the algorithm.
|
|
|
Non-Returning Turing Machines
Surovič, Marek ; Vrábel, Lukáš (referee) ; Meduna, Alexandr (advisor)
This work introduces a restricted variant of the Turing machine which cannot move left, thus return on its tape. Other properties, such as the potentially infinite symbol tape or the ability to rewrite symbols on the tape, remain unchanged. By introducing this restriction we limit the expressive power of the Turing machine to the point, where a non-returning Turing machine is equivalent to a finite automaton and can be transformed into one. A transformation algorithm is presented and described in detail.
|
|
| |
|
|
Compiler of Language of Mathematical Function
Junek, Lukáš ; Horáček, Petr (referee) ; Čermák, Martin (advisor)
In this thesis, we are dealing with construction of Interpreter of Language of Mathematical function. We constructed all parts of interpreter, which involved processing and execution of source code. The main part of my thesis is implementation of computer operations with matrices using SSE instructions. For this purpose, we used interface by Intel. There in a special header file are defined the functions corresponding to each instruction. However, functions not only to calculate, but perform support operations, which eliminate some annoying features of assembler.
|
|
|
Hardware Acceleration of Cipher Attack
Okuliar, Adam ; Slaný, Karel (referee) ; Vašíček, Zdeněk (advisor)
Hardware acceleration is often good tool to achieve significantly better performance of processing great ammount of data or of realization of parallel algoritms. Aim of this work is to demonstrate resoluts of using FPGA circuits for implementation exponentially complex algorithm. As example haschosen brute-force attack on WEP cryptographic algorithm with 40-bit long key. Goal of this work is to compare properties and performance of software and hardware implementation of choosen algorithm.
|
|
|
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.
|
|
|
Library for Operations over Finite Automata
Bartůněk, Petr ; Puš, Viktor (referee) ; Kaštil, Jan (advisor)
This work deals with two basic operations over finite automata. Determination of nondeterministic finite automata and minimization of deterministic finite automata. For these two operations I proposed sequential algorithms that are parallelizable. I deal mainly with finding the speedup of SSE instructions, or use the OpenMP library. The trend today is mainly in increasing the number of processors, so I propose parallel algorithms for multiple processors. When searching for the optimal solution, I will be to examine other ways to achieve speedup, for example efficient saving of the data structures in memory.
|
|
|
Model Checking Infinite-State Systems Using Language Inference
Rozehnal, Pavel ; Křena, Bohuslav (referee) ; Vojnar, Tomáš (advisor)
Regular model checking is a method for verifying infinite-state systems based on coding their configurations as words over a finite alphabet, sets of configurations as finite automata, and transitions as finite transducers. We implement regular model checking using inference of regular languages. The method builds upon the observations that for infinite-state systems whose behavior can be modeled using length-preserving transducers, there is a finite computation for obtaining all reachable configurations. Our new approach to regular model checking via inference of regular languages is based on the Angluin's L* algorithm that is used for finding out an invariant which can answer our question whether the system satisfies some property. We also provide an intro to the theory of finite automata, model checking, SAT solving and Anguin's L* and Bierman algorithm of learning finite automata.
|
|
|
Implementation of General Disassembler
Přikryl, Zdeněk ; Masařík, Karel (referee) ; Lukáš, Roman (advisor)
This thesis presents the process of creating disassembler for new designed processors. We demand automatic generation of the disassembler. Instruction set for processor is modeled by specialized language ISAC, which offers resources for description of the instruction set. For example it describes format of instruction in the assembly language or format of instruction in the binary form or behavior of this instruction. Internal model is coupled finite automata, which describes relation of textual form of the instruction and binary form of the instruction in formal way. The code of disassembler is generated from the internal model. This disassembler accepts program in binary code at the input and generate equivalent program in assembly language at the output.
|
|
|
Automatic Generator of Diacritics
Veselý, Lukáš ; Sumec, Stanislav (referee) ; Smrž, Pavel (advisor)
The goal of this diploma work is the suggestion and the implementation of the application, which allows adding / removing of diacritics into / from Czech written text. Retrieval "trie" structure is described along with its relation to finite state automata. Further, algorithm for minimization of finite state automata is described and various methods for adding diacritics are discussed. In practical part the implementation in Java programming language with usage of object-oriented approach is given. Achieved results are evaluated and analysed in the conclusion.
|
guest ::
