Konečné automaty jsou základní modely používané v informatice a teorii výpočtů využíva-né k analýze a řešení různých výpočetních problémů. Tradiční konečné automaty však mají určitá omezení ve své vyjadřovací schopnosti, zejména při řešení složitých problémů s nelokálními závislostmi. Toto vedlo k vývoji skákající konečných automatů jako rozšíření tradičních modelů, které poskytují větší výpočetní možnosti.
Tato bakalářská práce se zabývá skákajícími konečnými automaty, což jsou rozšířené mode-ly konečných automatů umožňujících přeskakování libovolného počtu symbolů v řetězci. Skákající konečné automaty poskytují zvýšenou výpočetní sílu a jsou vhodné pro řešení problémů s nesousedními závislostmi.
V teoretické části práce se zaměřujeme na formální popis skákajících konečných automatů, včetně jejich definice, pravidel přechodů a vlastností. Analyzujeme rozdíly mezi skákajícími konečnými automaty a tradičními konečnými automaty, definujeme modely skákajících konečných automatů a jejich vlastnosti.
V praktické části práce vyvíjíme demonstrační aplikaci nazvanou JFA Simulator, která umožňuje vizualizaci a experimentování se skákajícími konečnými automaty. Aplikace umožňuje uživatelům zadávat zápis skákajících konečných automatů a sledovat jejich vý-početní chod. Díky grafickému zobrazení automatu si uživatelé mohou lépe představit a porozumět výpočtům skákajících konečných automatů.
Výsledkem práce je teoretický popis skákajících konečných automatů a jejich implementace v podobě demonstrační aplikace JFA Simulator. Naše práce poskytuje užitečný nástroj pro zkoumání a experimentování s těmito rozšířenými modely automatů, a přispívá tak k lepší-mu porozumění jejich výpočetních možností.
Anotace v angličtině
Finite automata are basic models used in computer science and computational theory to analyze and solve various computational problems. However, traditional finite automata have some limitations in their expressive power, especially when solving complex problems with nonlocal dependencies. This has led to the development of jumping finite automata as an extension of traditional models to provide greater computational capabilities.
This thesis deals with jumping finite automata, which are extended models of finite auto-mata that allow skipping of any number of symbols in a string. Jumping finite automata provide increased computational power and are suitable for solving problems with nonadja-cent dependencies.
In the theoretical part of the paper, we focus on the formal description of jumping finite automata, including their definition, transition rules and properties. We analyze the diffe-rences between jumping finite automata and traditional finite automata, and define models of jumping finite automata and their properties.
In the practical part of the work, we develop a demonstration application called JFA Simu-lator that allows visualization and experimentation with jumping finite automata. The ap-plication allows users to enter the notation of jumping finite automata and observe their computational operation. With a graphical representation of the automaton, users can better visualize and understand the computation of jumping finite automata.
The result of this work is a theoretical description of jumping finite automata and its im-plementation in the form of a JFA Simulator demonstration application. Our work provides a useful tool for exploring and experimenting with these extended models of automata, thus contributing to a better understanding of their computational capabilities.
Klíčová slova
konečné automaty, skákající konečné automaty, vizualizace, demonstrační aplikace
Konečné automaty jsou základní modely používané v informatice a teorii výpočtů využíva-né k analýze a řešení různých výpočetních problémů. Tradiční konečné automaty však mají určitá omezení ve své vyjadřovací schopnosti, zejména při řešení složitých problémů s nelokálními závislostmi. Toto vedlo k vývoji skákající konečných automatů jako rozšíření tradičních modelů, které poskytují větší výpočetní možnosti.
Tato bakalářská práce se zabývá skákajícími konečnými automaty, což jsou rozšířené mode-ly konečných automatů umožňujících přeskakování libovolného počtu symbolů v řetězci. Skákající konečné automaty poskytují zvýšenou výpočetní sílu a jsou vhodné pro řešení problémů s nesousedními závislostmi.
V teoretické části práce se zaměřujeme na formální popis skákajících konečných automatů, včetně jejich definice, pravidel přechodů a vlastností. Analyzujeme rozdíly mezi skákajícími konečnými automaty a tradičními konečnými automaty, definujeme modely skákajících konečných automatů a jejich vlastnosti.
V praktické části práce vyvíjíme demonstrační aplikaci nazvanou JFA Simulator, která umožňuje vizualizaci a experimentování se skákajícími konečnými automaty. Aplikace umožňuje uživatelům zadávat zápis skákajících konečných automatů a sledovat jejich vý-početní chod. Díky grafickému zobrazení automatu si uživatelé mohou lépe představit a porozumět výpočtům skákajících konečných automatů.
Výsledkem práce je teoretický popis skákajících konečných automatů a jejich implementace v podobě demonstrační aplikace JFA Simulator. Naše práce poskytuje užitečný nástroj pro zkoumání a experimentování s těmito rozšířenými modely automatů, a přispívá tak k lepší-mu porozumění jejich výpočetních možností.
Anotace v angličtině
Finite automata are basic models used in computer science and computational theory to analyze and solve various computational problems. However, traditional finite automata have some limitations in their expressive power, especially when solving complex problems with nonlocal dependencies. This has led to the development of jumping finite automata as an extension of traditional models to provide greater computational capabilities.
This thesis deals with jumping finite automata, which are extended models of finite auto-mata that allow skipping of any number of symbols in a string. Jumping finite automata provide increased computational power and are suitable for solving problems with nonadja-cent dependencies.
In the theoretical part of the paper, we focus on the formal description of jumping finite automata, including their definition, transition rules and properties. We analyze the diffe-rences between jumping finite automata and traditional finite automata, and define models of jumping finite automata and their properties.
In the practical part of the work, we develop a demonstration application called JFA Simu-lator that allows visualization and experimentation with jumping finite automata. The ap-plication allows users to enter the notation of jumping finite automata and observe their computational operation. With a graphical representation of the automaton, users can better visualize and understand the computation of jumping finite automata.
The result of this work is a theoretical description of jumping finite automata and its im-plementation in the form of a JFA Simulator demonstration application. Our work provides a useful tool for exploring and experimenting with these extended models of automata, thus contributing to a better understanding of their computational capabilities.
Klíčová slova
konečné automaty, skákající konečné automaty, vizualizace, demonstrační aplikace
Popište teorii týkající se skákajících konečných automatů (dále SKA).
Do popisu zahrňte SKA obousměrné i jednosměrné, deterministické i nedeterministické.
Ve vhodném programovacím jazyce sestavte simulátor různých variant SKA.
Simulátor musí umožňovat jednoduché zadávání SKA ve zvolené variantě, jejich editaci a názornou vizualizaci jejich činnosti.
Zásady pro vypracování
Popište teorii týkající se skákajících konečných automatů (dále SKA).
Do popisu zahrňte SKA obousměrné i jednosměrné, deterministické i nedeterministické.
Ve vhodném programovacím jazyce sestavte simulátor různých variant SKA.
Simulátor musí umožňovat jednoduché zadávání SKA ve zvolené variantě, jejich editaci a názornou vizualizaci jejich činnosti.
Seznam doporučené literatury
H. CHIGAHARA, S. Z. FAZEKAS, a A. YAMAMURA: "One-way jumping finite automata", International Journal of Foundations of Computer Science, díl 27, 2016, str. 391-405.
E. CSUHAJ-VARJÚ, C. MARTÍN-VIDE a V. MITRANA: "Multiset automata" v Multiset processing — mathematical, computer science, and molecular computing points of view, C. S. CALUDE, G. PAUN, G. ROZENBERG a A. SALOMAA, Ed., Lecture notes in computer science, díl 2235, Berlín: Springer, 2001, str. 69–83.
ČERNÁ, Ivana, a kol.: Automaty a formální jazyky I. Učební text FI MU. Fakulta informatiky, Masarykova univerzita, Brno: 2002. Dostupné z: http://is.muni.cz/elportal/estud/fi/js06/ib005/Formalni_jazyky_a_automaty_I.pdf
A. MEDUNA a P. ZEMEK: "Jumping finite automata", International Journal of Foundations of Computer Science, díl 23, 2012, str. 1555-1578.
M. SIPSER, Introduction to the Theory of Computation, 2. vyd., Boston: Thomson Course Technology, 2006.
Seznam doporučené literatury
H. CHIGAHARA, S. Z. FAZEKAS, a A. YAMAMURA: "One-way jumping finite automata", International Journal of Foundations of Computer Science, díl 27, 2016, str. 391-405.
E. CSUHAJ-VARJÚ, C. MARTÍN-VIDE a V. MITRANA: "Multiset automata" v Multiset processing — mathematical, computer science, and molecular computing points of view, C. S. CALUDE, G. PAUN, G. ROZENBERG a A. SALOMAA, Ed., Lecture notes in computer science, díl 2235, Berlín: Springer, 2001, str. 69–83.
ČERNÁ, Ivana, a kol.: Automaty a formální jazyky I. Učební text FI MU. Fakulta informatiky, Masarykova univerzita, Brno: 2002. Dostupné z: http://is.muni.cz/elportal/estud/fi/js06/ib005/Formalni_jazyky_a_automaty_I.pdf
A. MEDUNA a P. ZEMEK: "Jumping finite automata", International Journal of Foundations of Computer Science, díl 23, 2012, str. 1555-1578.
M. SIPSER, Introduction to the Theory of Computation, 2. vyd., Boston: Thomson Course Technology, 2006.
Přílohy volně vložené
-
Přílohy vázané v práci
-
Převzato z knihovny
Ne
Plný text práce
Přílohy
Posudek(y) oponenta
Hodnocení vedoucího
Záznam průběhu obhajoby
Student seznámil komisi s výsledky své bakalářské práce. Poté byly prezentovány posudky vedoucího a oponenta a následně byla vedena rozprava, během které byly položeny následující otázky a komentáře:
Student se zdařilým způsobem vypořádal s absencí jakýchkoli česky psaných materiálů, které by se týkaly skákajících konečných automatů. U obhajoby by však měl opravit příklad nedeterministického konečného automatu ze str. 16, který nepřijímá deklarovaný jazyk. (dr. Martinek)
Na obrázku 4 máte automat, o kterém tvrdíte, že přijímá slova obsahující 01 nebo 10. Tato slova však nepřijímá, protože například nepřijímá slovo 10, ani slovo 0101. Jaké slova tedy přijímá?
Jak by vypadal automat, který skutečně odpovídá popisu? Proč je automat z obr. 4 nedeterministický? Odpovídá to vaší definici nedeterministického konečného automatu ze sekce 1.3? Ve vaší aplikaci deterministický skákající obousměrný konečný automat přijímá následující
konfiguraci: Specified alphabet: [’A’, ’B’]
Specified input str: [’A’, ’B’]
Specified states: [’q’, ’s’, ’r’, ’t’]
Specified starting state: q
Specified end states: [’t’]
Specified jumps: [[’q’, ’A’, ’s’], [’s’, ’A’, ’r’], [’r’, ’B’, ’t’]]
Je to v pořádku? Pokud není, jak došlo k této chybě a jak by se tato chyba odstranila? (dr. Krňávek)
Doporučení pro příště - Netiskněte kód v černém pozadí a obrázky nezvětšujte podle šířky stránky. Načítáte sice automat, ale který stav je zobrazen? Provádíte to automaticky? Vysvětlete. Mohl jste použít JSON. Znak + řeší problém prvního opakování (prof. Platoš)
Student pohotově reagoval a všechny otázky správně zodpověděl.