|
|
Synchronizace konečných automatů
Vorel, Vojtěch ; Koubek, Václav (vedoucí práce) ; Pangrác, Ondřej (oponent)
Práce je úvodem do zkoumání synchronizačních slov konečných automatů a Černého domněnky. Podává přehled o důležitých výsledcích v oboru a metodách jejich dokazování, ale také o širokém spektru dosud nevyřešených otázek. Reprodukuje i důkazy některých nejnovějších výsledků, konkrétně Trakhtmanova horního odhadu obecného sycnhronizačního prahu a Steinbergova těsného odhadu pro jednoklastrové automaty s prvočíselnou délkou cyklu. V poslední kapitole se blíže zaměřujeme na problém synchronizace podmnožin a související výpočetní úlohy. Je zde prezentován nový dolní odhad maximálního synchronizačního prahu podmnožiny. Podařilo se také částečně určit časovou složitost jisté přirozeně omezené varianty PSPACE-úplné úlohy rozhodování o synchronizovanosti podmnožiny.
|
|
| |
|
|
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.
|
|
|
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í.
|
|
|
Konstrukce zobecněného konečného automatu
Šoka, Martin ; Košař, Vlastimil (oponent) ; Kaštil, Jan (vedoucí práce)
Práce se zabývá vytvořením algoritmu pro konstrukci deterministického zobecněného konečného automatu. Tento automat se od obyčejného deterministického automatu liší tím, že jeho přechody jsou definovány slovy, na základě čeho je možné zredukovat počet stavů obyčejného deterministického automatu. V úvodě jsou vysvětleny základní pojmy, které jsou dále v práci používány. Dále práce popisuje algoritmus samotný, včetně podrobného popisu heuristiky k vyhledání maximálního acyklického podgrafu v grafu atomatu. Popsána je implementace algoritmu a experimentování s algoritmem vytvořenými automaty.
|
|
|
Turingovy stroje bez návratu na pásce
Surovič, Marek ; Vrábel, Lukáš (oponent) ; Meduna, Alexandr (vedoucí práce)
Tato práce zavádí omezenou variantu Turingových strojů, které se nemohou pohybovat doleva, tedy se vracet na pásce. Ostatní vlastnosti Turingových strojů (například potenciálně nekonečná páska a schopnost přepisovat symboly na pásce) jsou zachovány. Zavedením tohoto omezení limitujeme vyjadřovací sílu Turingových strojů do té míry, ľe Turingovy stroje bez návratu na pásce jsou ekvivalentní s konečnými automaty a lze je na konečný automat transformovat. Dále je představen a detailně popsán algoritmus, který realizuje tuto transformaci.
|
|
| |
|
|
Měření spolehlivosti vyhledávání vzorů
Dvořák, Milan ; Košař, Vlastimil (oponent) ; Kaštil, Jan (vedoucí práce)
Tato práce se zabývá metodami vyhledávání vzorů pomocí konečných automatů a popisuje některé optimalizace těchto algoritmů. Dále rozebírá návrh a implementaci metodiky pro měření spolehlivosti vyhledávání na základě srovnávání s výsledky PCRE knihovny. Experimentální měření byla provedena pro konečný automat s perfektním hašováním a chybující přechodovou tabulkou. Nakonec je prezentováno výsledné hodnocení spolehlivosti algoritmu spolu s návrhem řešení zjištěných problémů.
|
|
|
Hledání regulárních výrazů s využitím technologie FPGA
Kaštil, Jan ; Martínek, Tomáš (oponent) ; Kořenek, Jan (vedoucí práce)
V práci je vysvětluje několik algoritmů pro vyhledávání výrazů v textu. Algoritmy pracují v software i hardware. Část práce se zabývá rozšířením konečných automatů. Další část práce vysvětluje, jak funguje hash a představuje koncept perfektního hashování a CRC. Součástí práce je návrh možné struktury vyhledávací jednotky založené na deterministických konečných automatech v FPGA. V rámci práce byly provedeny exprimenty pro zjištění podoby výsledných konečných automatů.
|
|
|
Syntaktická analýza založená na párových automatech
Zámečníková, Eva ; Masařík, Karel (oponent) ; Lukáš, Roman (vedoucí práce)
Diplomová práce pojednává o syntaktické analýze založené na modelu párových automatů. Konečný párový automat obsahuje vstupní a výstupní automat. Vstupní automat provádí syntaktickou analýzu se vstupním řetězcem. Použitá pravidla vstupního automatu řídí výstupní automat, který generuje výstupní řetězec. V práci je popsán způsob determinizace vstupního automatu bez ztráty informací o pravidlech použitých v původním automatu. Determinizace je rozdělena na dvě části - pro převodníky specifikující konečný a nekonečný překlad. Dále je prezentován párový automat se zvýšenou výpočetní silou. Zvýšení síly spočívá v nahrazení vstupního či výstupního automatu nebo jen jeho části bezkontextovou gramatikou.
|
host ::
RSS.