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í.
Annotation in English
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.
Keywords
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í.
Annotation in English
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.
Keywords
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.
Research Plan
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.
Recommended resources
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.
Recommended resources
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.
