Vizualizace skákajících konečných automatů

Abstract

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í.