Název: Efektivní redukce konečných automatů
Překlad názvu: Efficient Reduction of Finite Automata
Autoři: Molnárová, Veronika ; Havlena, Vojtěch (oponent) ; Lengál, Ondřej (vedoucí práce)
Typ dokumentu: Bakalářské práce
Rok: 2023
Jazyk: eng
Nakladatel: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstrakt: [eng] [cze]
Konečný stavový automat je matematický model popisujúci stroj vykonávajúci výpočet na zadanom vstupe cez postupnosť stavov. Za posledné storočie si tento koncept našiel využitie v rôznych odvetviach informatiky od správania postáv vo videohrách po kompilátory. Pokým automat popisuje jeden jazyk, ten môže byť reprezentovaný nekonečným množstvom rôznych automatov. Keďže veľkosť týchto automatov sa líši, pre zaistenie čo najefektívnejšej práce chceme nájsť ten najmenší z nich. V tejto práci sa pozrieme na päť rôznych typov redukcie automatov. Najskôr sa budeme zaoberať troma známymi redukčnými algoritmami, menovite to bude minimalizácia deterministického automatu, redukcia pomocou relácie simuláciu a redukcia pomocou prevodu na kanonický reziduálny automat. Tieto redukcie boli implementované v jazyku C++ a otestované na skúšobnom vzorku automatov pre porovnanie výsledkov jednotlivých redukcií. Posledne sme sa pozreli na možnosť redukovať konečný stavový automat pomocou SAT a QBF solverov. Vytvorili sme množinu pravidiel pre každý solver pre tvorbu klauzule v konjunktnej normálnej forme, ktorá dokáže jednoznačne reprezentovať automat v Booleovej algebre. S využitím tohto faktu sme vytvorili nový spôsob redukcie nedeterministického automatu. A finite state automaton is a mathematical model used to describe a machine that performs a computation on the given input over a series of states. In the last century, it has found many uses in different fields of information technology, from video game character behavior to compilers. While each automaton denotes its language, one language can be represented by an infinite number of different automata. As these automata vary in size, to ensure the most efficient work with them, we want to find the smallest one possible. In this thesis, we are going to look at five different types of automata reductions. Firstly, we will talk about three known reduction algorithms, which are the minimization of deterministic automata, the reduction based on a relation of simulation, and the reduction by transformation into a canonical residual automaton. These reductions were implemented in C++ and tested on a sample set of automata to compare their results. Lastly, we looked at the possibility of reducing finite state automata using Boolean satisfiability problem (SAT) and quantified Boolean formula (QBF) solvers. We are presenting a set of rules for each solver for generating a clause in conjunctive normal form (CNF), which can precisely represent the given automaton in Boolean algebra. We used this fact to create a new method of nondeterministic automata reduction.
Klíčová slova: automata reduction; finite state automata; minimal deterministic automata; QBF solver; residual automata; SAT solver; simulation; konečné stavové automaty; minimálny deterministický automat; QBF solver; redukcia automatov; reziduálny automat; SAT solver; simulácia

Instituce: Vysoké učení technické v Brně (web)
Informace o dostupnosti dokumentu: Plný text je dostupný v Digitální knihovně VUT.
Původní záznam: http://hdl.handle.net/11012/212706

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-530935


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Vysoké učení technické v Brně
Vysokoškolské kvalifikační práce > Bakalářské práce