Original title: Centralizované verze skákajících automatů
Translated title: Centralized Versions of Jumping Automata
Authors: Foltýn, Zdeněk ; Klembara, Radovan (referee) ; Meduna, Alexandr (advisor)
Document type: Bachelor's theses
Year: 2025
Language: eng
Publisher: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract: [eng] [cze]
Tato práce zavádí centralizované obecné skákající konečné automaty (CGJFA), nový model výpočtu založený na obecných skákajících automatech. CGJFA čtou podřetězce vstupu obsahující speciální centrální symbol #, který je do řetězce vložen před začátkem výpočtu. Řetězec je přijat, pokud opakovaným mazáním zůstane na pásce pouze #. Formálně jsou definovány CGJFA a jejich omezená varianta CJFA a je dokázáno, že rozpoznávají právě lineární jazyky. Dále jsou představeny jednostavové a vyvážené CGJFA, které charakterizují minimální a sudé lineární jazyky. Součástí práce je také implementace simulátoru v jazyce Python s rozhraním příkazové řádky a grafickým zobrazením výpočtu. Na závěr jsou identifikovány otevřené otázky, týkající se deterministických variant, rozšíření o zásobník a alternativního režimu výpočtu. This thesis introduces centralized general jumping finite automata (CGJFA), a computational model based on general jumping automata. CGJFAs delete substrings of the input that contain a special central symbol # inserted once before computation begins. A string is accepted if repeated deletions reduce it to # alone. CGJFAs and their restricted version, CJFAs, are formally defined, and it is shown that they recognize exactly the class of linear languages. Additional variants, including one-state and balanced CGJFAs, are introduced and shown to characterize minimal and even linear languages, respectively. A Python-based simulator is also presented, featuring a command-line interface and graphical visualization of computation. Finally, several open problems are identified, including determinization, pushdown extensions, and alternative modes of operation.
Keywords: diskontinuální výpočty; lineární jazyky; minimální lineární jazyky; přijímání lineárních jazyků; simulace automatů; skákající konečné automaty; sudé lineární jazyky; teorie formálních jazyků; acceptance of linear languages; discontinuous computation; even linear languages; formal language theory; jumping finite automata; linear languages; minimal linear languages; simulating automata

Institution: Brno University of Technology (web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library.
Original record: http://hdl.handle.net/11012/255452

Permalink: http://www.nusl.cz/ntk/nusl-688045


The record appears in these collections:
Universities and colleges > Public universities > Brno University of Technology
Academic theses (ETDs) > Bachelor's theses