|
|
Reduction of the Nondeterministic Finite Automata
Procházka, Lukáš ; Kořenek, Jan (referee) ; Kaštil, Jan (advisor)
Nondeterministic finite automaton is an important tool, which is used to process strings in many different areas of programming. It is important to try to reduce its size for increasing programs' effectiveness. However, this problem is computationally hard, so we need to search for new techniques. Basics of finite automata are described in this work. Some methods for their reduction are then introduced. Usable reduction algorithms are described in greater detail. Then they are implemented and tested. The test results are finally evaluated.
|
|
|
Fast Regular Expression Matching Using FPGA
Kubiš, Juraj ; Fukač, Tomáš (referee) ; Matoušek, Denis (advisor)
Bachelor thesis deals with the possibility of hardware acceleration of regular expression matches. The content of the thesis is to analyze existing hardware architectures and evaluate their positive and negative properties. Based on this knowledge, the architecture is designed. It is based on deterministic finite automata with implicit transitions (D2FA), is implemented in VHDL and is synthesized. The synthesis results are analyzed to determine the overall throughput of the architecture. It is designed software to convert regular expressions into a D2FA and to optimize this automaton in order to minimize memory requirements. The implementation is verified and the benefits of individual optimization techniques to reduce memory requirements are evaluated.
|
|
|
Vizualization of Automata Algorithms
Kuchyňka, Jiří ; Češka, Milan (referee) ; Holík, Lukáš (advisor)
Tato práce se zabývá návrhem a implementací generického systému k vizualizaci algoritmů, které pracují nad automaty. Výsledný systém zcela odděluje část, která se věnuje generování dat k vizualizaci a část, která se věnuje vizualizování. Systém pouze určuje jejich komunikační rozhraní. Práce se zaměřuje na integraci takovéhoto systému do existujících knihoven takovým způsobem, aby byly minimalizovány požadavky na programátora, k tomu aby mohl vizualizovat stav svého algoritmu. Práce se také zkráceně věnuje možnostem využití tohoto systému k vizualizaci stavu algoritmu při krokování programem během ledění. Navržený systém může být použit pro výuku, výzkum a praktické aplikace v oblasti teorie automatů. V budoucnu by mohl být systém rozšířen o nástroje k vizualizaci turingových strojů a algoritmů pracujících nad nimi.
|
|
|
Fast Regular Expression Matching Using FPGA
Kubiš, Juraj ; Fukač, Tomáš (referee) ; Matoušek, Denis (advisor)
Bachelor thesis deals with the possibility of hardware acceleration of regular expression matches. The content of the thesis is to analyze existing hardware architectures and evaluate their positive and negative properties. Based on this knowledge, the architecture is designed. It is based on deterministic finite automata with implicit transitions (D2FA), is implemented in VHDL and is synthesized. The synthesis results are analyzed to determine the overall throughput of the architecture. It is designed software to convert regular expressions into a D2FA and to optimize this automaton in order to minimize memory requirements. The implementation is verified and the benefits of individual optimization techniques to reduce memory requirements are evaluated.
|
|
|
Reduction of the Nondeterministic Finite Automata
Procházka, Lukáš ; Kořenek, Jan (referee) ; Kaštil, Jan (advisor)
Nondeterministic finite automaton is an important tool, which is used to process strings in many different areas of programming. It is important to try to reduce its size for increasing programs' effectiveness. However, this problem is computationally hard, so we need to search for new techniques. Basics of finite automata are described in this work. Some methods for their reduction are then introduced. Usable reduction algorithms are described in greater detail. Then they are implemented and tested. The test results are finally evaluated.
|
guest ::
