Restartovací automaty s h-lexikalizací
On h-lexicalized Automata
bachelor thesis (DEFENDED)

View/ Open
Permanent link
http://hdl.handle.net/20.500.11956/200890Identifiers
Study Information System: 271227
Collections
- Kvalifikační práce [11606]
Author
Advisor
Consultant
Plátek, Martin
Referee
Mráz, František
Faculty / Institute
Faculty of Mathematics and Physics
Discipline
Computer Science with specialisation in Foundations of Computer Science
Department
Department of Theoretical Computer Science and Mathematical Logic
Date of defense
20. 6. 2025
Publisher
Univerzita Karlova, Matematicko-fyzikální fakultaLanguage
Czech
Grade
Good
Keywords (Czech)
restartovací automat|h-lexikalizovaný automat|vlastnost zachování správnosti|vlastnost zachování chyby|lexikální disambiguace|redukční analýzaKeywords (English)
lexicalized syntactic analysis|restarting automaton|correctness preserving computation|error preserving computation|analysis by reductionTato 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.