Restartovací automaty s h-lexikalizací

Abstract

Tato bakalářská práce představuje nový výpočetní model označovaný jako h-lexikali- zovaný tvrdě restartující seznamový automat (LxHRLAW). Model rozšiřuje klasické re- startovací automaty tím, že zavádí lexikální omezení pomocí h-morfismu a definuje dva typy restartovacích operací: běžné restarty pro iterativní fáze anotace a analýzy, a tvrdé restarty pro lexikální normalizaci. Práce zkoumá, jak tyto strukturované fáze anotace a redukce umožňují robustní a správnost zachovávající lingvistickou analýzu. Praktické vý- početní příklady, včetně binárního sčítání a konkatenace řetězců, demonstrují schopnost automatu sloužit jako funkční výpočetní zařízení s výstupem. Součástí práce je imple- mentace tohoto modelu v podobě demonstračního programu napsaného v Pythonu.

This bachelor thesis introduces a computational model known as the h-lexicalized Hard Restarting List Automaton (LxHRLAW). The model extends classical restarting automata by incorporating lexical constraints through an h-morphism and by defining two distinct restart operations: regular restarts for iterative annotation and analysis phases, and hard restarts for lexical normalization. This thesis explores how these structured phases of annotation and reduction enable robust and correctness-preserving linguistic analyses. Practical computational examples, including binary addition and string con- catenation, illustrate the automaton's capacity as a functional computational device with output capabilities. A Python-based proof-of-concept implementation accompanies this thesis to demonstrate practical feasibility.