|
|
Demonstrace skákajících automatů
Růžička, Ladislav ; Kocman, Radim (oponent) ; Křivka, Zbyněk (vedoucí práce)
Tato práce se zabývá demonstrací nově zkoumaného výpočetního modelu pro popis formálních jazyků, a to skákajícího automatu. Místo souvislého čtení vstupního řetězce, jak je tomu u konvenčních konečných automatů, tak u skákajícího automatu je proveden skok přes nějaké symboly, a poté je přečten symbol. V této práci se zejména budeme zabývat hledáním praktického algoritmu pro určení problému členství vstupního řetězce do jazyka popsaného skákajícím automatem. Ukážeme, že problém členství může být redukován na problém hledání nějakého nezáporného celočíselného řešení pro formuli v Presburgové aritmetice bez kvantifikátorů. Z této formule jsme schopni jednoznačně definovat jazyk přijímaný skákajícím automatem. Najdeme podmnožinu takových skákajících automatů, pro které lze vyřešit problém členství v polynomiálním čase. Zmíníme se také, že předchozí formule lze převést na konečný automat s více čtecími hlavami. Bohužel pro problém členství obecného skákajícího automatu hledání nezáporné číselného řešení je nedostačující, nicméně metoda může zmenšit prohledávaný stavový prostor. Uvedeme další možné heuristiky, které výrazně urychlují výpočet problému členství pro obecné skákající automaty.
|
|
|
Prostředí pro podporu modelů formálních jazyků
Juda, Jan ; Kocman, Radim (oponent) ; Křivka, Zbyněk (vedoucí práce)
Cílem této práce je vytvořit podpůrné prostředí pro spouštění algoritmů a výpočet typických problémů na pokročilých modelech formálních jazyků. Toto prostředí je realizováno jako modulární aplikace s využitím OSGi rámce, u které autor dbá na snadnou integraci nových uživatelem definovaných modelů formálních jazyků a algoritmů pro tyto modely, a to bez nutnosti úprav či opětovného překladu ostatních částí prostředí včetně jeho jádra. Pro demonstrování svých možností podpůrné prostředí obsahuje implementaci konečného automatu, bezkontextové gramatiky, n-zásobníkového m-páskového automatu, obecného skákajícího konečného automatu, Watson-Crickova konečného automatu, problému členství a algoritmů obecně schopných řešit problém členství na automatech a gramatikách.
|
|
|
Demonstrace skákajících automatů
Růžička, Ladislav ; Kocman, Radim (oponent) ; Křivka, Zbyněk (vedoucí práce)
Tato práce se zabývá demonstrací nově zkoumaného výpočetního modelu pro popis formálních jazyků, a to skákajícího automatu. Místo souvislého čtení vstupního řetězce, jak je tomu u konvenčních konečných automatů, tak u skákajícího automatu je proveden skok přes nějaké symboly, a poté je přečten symbol. V této práci se zejména budeme zabývat hledáním praktického algoritmu pro určení problému členství vstupního řetězce do jazyka popsaného skákajícím automatem. Ukážeme, že problém členství může být redukován na problém hledání nějakého nezáporného celočíselného řešení pro formuli v Presburgové aritmetice bez kvantifikátorů. Z této formule jsme schopni jednoznačně definovat jazyk přijímaný skákajícím automatem. Najdeme podmnožinu takových skákajících automatů, pro které lze vyřešit problém členství v polynomiálním čase. Zmíníme se také, že předchozí formule lze převést na konečný automat s více čtecími hlavami. Bohužel pro problém členství obecného skákajícího automatu hledání nezáporné číselného řešení je nedostačující, nicméně metoda může zmenšit prohledávaný stavový prostor. Uvedeme další možné heuristiky, které výrazně urychlují výpočet problému členství pro obecné skákající automaty.
|
host ::
RSS.