Original title: Symbolická reprezentace konečných automatů
Translated title: Symbolic Representation of Finite Automata
Authors: Chromečka, Jiří ; Vojnar, Tomáš (referee) ; Lengál, Ondřej (advisor)
Document type: Bachelor's theses
Year: 2014
Language: cze
Publisher: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract: [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.
Keywords: binary decision diagram; finite automaton; language intersection; language union; libVATA library; simulation relation; symbolic representation; binární rozhodovací diagram; jazykové sjednocení; jazykový průnik; knihovna libVATA; konečný automat; relace simulace; symbolická reprezentace

Institution: Brno University of Technology (web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library.
Original record: http://hdl.handle.net/11012/56500

Permalink: http://www.nusl.cz/ntk/nusl-239650


The record appears in these collections:
Universities and colleges > Public universities > Brno University of Technology
Academic theses (ETDs) > Bachelor's theses