Název: Symbolická reprezentace konečných automatů
Překlad názvu: Symbolic Representation of Finite Automata
Autoři: Chromečka, Jiří ; Vojnar, Tomáš (oponent) ; Lengál, Ondřej (vedoucí práce)
Typ dokumentu: Bakalářské práce
Rok: 2014
Jazyk: cze
Nakladatel: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstrakt: [cze] [eng]
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. 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.
Klíčová slova: binární rozhodovací diagram; jazykové sjednocení; jazykový průnik; knihovna libVATA; konečný automat; relace simulace; symbolická reprezentace; binary decision diagram; finite automaton; language intersection; language union; libVATA library; simulation relation; symbolic representation

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/56500

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


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