Original title: Efektivní algoritmy pro konečné automaty
Translated title: Efficient Algorithms for Finite Automata
Authors: Kantor, Tomáš ; Rogalewicz, Adam (referee) ; Lengál, Ondřej (advisor)
Document type: Bachelor's theses
Year: 2021
Language: cze
Publisher: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract: [cze] [eng]
Tato práce prezentuje nový algoritmus pro komplementaci nedeterministických konečných automatů. Současné metody vyžadují převod na deterministický konečný automat, který může mít exponenciálně větší počet stavů. Navržený algoritmus pracuje iterativně po jednotlivých silně souvislých komponentách konečného automatu. Díky tomu umožňuje jednotlivé části efektivněji komplementovat, redukovat a následně propojit s ostatními částmi automatu. Tento algoritmus je tak efektivnější než současné metody pro určité typy konečných automatů.  This thesis presents new algorithm for complement of nondeterministic finite automata. State-of-the-art methods require conversion to deterministic finite automata, which can have exponentially larger number of states. This new algorithm works separately on each strongly connected component of finite automata. This approach allows to create complement of each component, reduce it and combine with other parts. This algorithm was proven to create less states for specific types of finite automata than existing methods.
Keywords: antichain; complement; finite automata; nondeterministic finite automata; antichain; doplněk; konečné automaty; nedeterministické konečné automaty

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

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


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