|
|
Simulace a protiřetězce pro efektivní práci s konečnými automaty
Holík, Lukáš ; Černá, Ivana (oponent) ; Jančar, Petr (oponent) ; Vojnar, Tomáš (vedoucí práce)
This thesis is focused on techniques for finite automata and their use in practice, with the main emphasis on nondeterministic tree automata. This concerns namely techniques for size reduction and language inclusion testing, which are two problems that are crucial for many applications of tree automata. For size reduction of tree automata, we adapt the simulation quotient technique that is well established for finite word automata. We give efficient algorithms for computing tree automata simulations and we also introduce a new type of relation that arises from a combination of tree automata downward and upward simulation and that is very well suited for quotienting. The combination principle is relevant also for word automata. We then generalise the so called antichain universality and language inclusion checking technique developed originally for finite word automata for tree automata. Subsequently, we improve the antichain technique for both word and tree automata by combining it with the simulation-based inclusion checking techniques, significantly improving efficiency of the antichain method. We then show how the developed reduction and inclusion checking methods improve the method of abstract regular tree model checking, the method that was the original motivation for starting the work on tree automata. Both the reduction and the language inclusion methods are based on relatively simple and general principles that can be further extended for other types of automata and related formalisms. An example is our adaptation of the reduction methods for alternating Büchi automata, which results in an efficient alternating automata size reduction technique.
|
|
|
Klasifikace a využití gramatik, jazyků a automatů
Jancek, Libor ; Novotná, Veronika (oponent) ; Bobalová, Martina (vedoucí práce)
Tato bakalářská práce se zabývá teorií jazyků, gramatik a automatů. Ukázky použití konečných automatů v praxi na názorných příkladech a vytvoření programu, pro firmu Paradise Casino Admiral a.s. . Účelem tohoto programu je vyplnění evidence docházky na základě rozpisu služeb, který musí navrhnout manažerka pro svoje oddělení každý měsíc. Tento program by měl manažerce usnadnit a hlavně urychlit práci, kterou doposud vykonávala ručně.
|
|
| |
|
|
Klasifikace jazyků, gramatik a automatů
Mocková, Ľubica ; Zimmerová, Barbora (oponent) ; Bobalová, Martina (vedoucí práce)
Tato práce je stručným přehledem základních typů jazyků, gramatik a automatů, jež jsou součástí teoretické informatiky. Práce obsahuje přehled teorie, vázané k danému tématu a příklady vážící se k teoretické části. Tato práce má sloužit jako studijní materiál pro studenty Fakulty podnikatelské pro předmět Diskrétní matematika. Dále může stejně dobře posloužit i studentům jiných vysokých škol a fakult, kteří mají ve svém studijním plánu předmět týkající se teorie gramatik a automatů.
|
|
|
Symbolická reprezentace konečných automatů
Chromečka, Jiří ; Vojnar, Tomáš (oponent) ; Lengál, Ondřej (vedoucí práce)
V~oblasti formální analýzy se často setkáváme s~konečnými automaty s~velkým množstvím stavů nad velkými abecedami. Jejich explicitní reprezentace může vyústit ve stavovou explozi a~tento problém může být vyřešen použitím symbolické reprezentace schopné pracovat s~celou množinou stavů najednou. Cílem této práce je rozšířit knihovnu libVATA o~podporu této reprezentace včetně algoritmů pro některé operace nad touto reprezentací. Předložený text se v~úvodu zabývá předpoklady nezbytnými pro pochopení konečných automatů a~binárních rozhodovacích diagramů, které se využívají pro jejich symbolickou reprezentaci. Dále jsou uvedeny některé existující knihovny pro práci s~konečnými automaty. Následuje jádro této práce, návrh symbolické reprezentace a~operací nad ní, které jsou poté implementovány jako rozšíření zmíněné knihovny. Výsledky testů dokazují, že symbolická reprezentace je zajímavou alternativou explicitní reprezentace.
|
|
|
Simulace líných konečných automatů
Vrábel, Lukáš ; Masařík, Karel (oponent) ; Lukáš, Roman (vedoucí práce)
Táto bakalárska práca popisuje matematický model lenivého konečného automatu a implementáciu jednoduchého simulačného programu postaveného na základoch tohoto automatu, ktorý demonštruje možnosti daného modelu. Taktiež sa zaoberá výhodami a nevýhodami oproti ostatným prístupom a implementáciám. Model lenivého konečného automatu poskytuje určité výhody z hladiska uživateľa, ktorý vďaka nemu dostáva do rúk väčšiu voľnosť pri definovaní pravidiel automatu.
|
|
|
Kontextem řízený lexikální analyzátor
Hatina, Peter ; Koutný, Jiří (oponent) ; Čermák, Martin (vedoucí práce)
Tato práce se věnuje základním principům lexikální analýzy a způsobu kontextového rozpoznání typu lexému v závislosti na jeho pozici ve zdrojovém souboru. V práci bude popsán princip lexikální analýzy, postup tvorby lexikálního analyzátoru a možné řešení kontextového rozlišení lexémů, založené na automatovém systému. Lexikální analyzátor je rozšířen o vlastnost rozpoznávat tokeny v blocích kódu dalších jazyků.
|
|
|
Paralelní lexikální analyzátor
Ježek, Lukáš ; Koutný, Jiří (oponent) ; Čermák, Martin (vedoucí práce)
Tato práce se zabývá generováním lexikálního analyzátoru, který analyzuje soubor paralelně, tj. několika vlákny. Analyzátor je vygenerován na základě regulárního jazyka a reprezentován konečným automatem s potřebnými funkcemi. Důraz je zde kladen právě na paralelní zpracování. Diskutuje možnost zpracování dopřednými a zpětnými vlákny. V implementaci byla zvolena metoda dopředných vláken. Rozebírá problémy, které se vyskytly při implementaci a způsobily, že výsledný program nedosáhl téměř žádného zrychlení.
|
|
|
Demonstrační program konverzí konečných automatů
Štorek, Vojtěch ; Novotný, Tomáš (oponent) ; Lukáš, Roman (vedoucí práce)
Cílem praktické části této práce je vytvořit program, který aplikuje teorii konečných automatů v praxi a dělá tak tuto teorii snadější k pochopení. Program umožňuje snadné vytváření konečných automatů, nad nimiž následně jednoduše, ale hlavně didakticky demostruje základní teoretické znalosti, jako jsou převody na speciální typy konečných automatů, ilustrace činnosti nebo vyjádření konečného automatu formou zdrojového souboru v jazyce C. V této technické zprávě se pokusím popsat, jak jsou jednotlivé klíčové částí aplikace implementovány.
|
|
|
Vyhledávání idiomů v textu
Seitler, Andrej ; Schmidt, Marek (oponent) ; Smrž, Pavel (vedoucí práce)
Cílem projektu je seznámení se z různymi způsoby vyhledávaní víceslovných výrazů v textu a vytvoření programu, který vyhledává výskyt idiomů ze vstupního souboru v korpusech. Program klade důraz na rychlost vyhledávání. Výstupem je nalezený idiom, počet výskytů v textu a výpis vět, kde lze daný idiom najít. Obsahuje knihovnu pro rozdělování textu na věty podle znaku konce vět.
|
host ::
RSS.