Original title: Regulované jazykové operace a jejich užití
Translated title: Regulated Language Operations and Their Use
Authors: Chocholatý, David ; Kožár, Tomáš (referee) ; Meduna, Alexandr (advisor)
Document type: Bachelor's theses
Year: 2023
Language: cze
Publisher: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract: [cze] [eng]
Tato práce představuje a studuje vymazávací systémy jako alternativní formální jazykový model k obecným skákajícím konečným automatům. Významným rozdílem oproti daným automatům je využití řídícího regulárního jazyka namísto stavového řízení v podobě obecného konečného automatu. Vymazávací systémy ponechávají práci s řetězci na vstupní pásce, přičemž samotné regulární jazyky mohou být přijímány klasickými konečnými automaty. Zároveň se zavedením nového formálního systému práce prokazuje jeho vztahy se známými jazykovými rodinami, rodinou jazyků zamíchání, Dyckovými jazyky a uzávěrové vlastnosti. Na základě formální specifikace vymazávacího systému je uvedeno více aplikací v oblasti bioinformatiky pro molekulární biologii, textových editorů a kompozičního šachu, včetně návrhu algoritmů a prezentování implementačního řešení. This thesis introduces and studies erasing systems as an alternative formal language model to general jumping finite automata. A significant difference compared to the given automata is the use of a control regular language instead of state control in the form of a general finite automaton. Erasing systems leave the string work on the input tape, whereas regular languages themselves can be accepted by classical finite automata. At the same time, with the introduction of a new formal system, the thesis demonstrates its relations with well-known language families, the family of shuffle languages, Dyck languages and closure properties. Based on the formal specification of the erasing system, multiple applications in bioinformatics for molecular biology, text editors and compositional chess are shown, including designing algorithms and presenting the implementation solution.
Keywords: application of formal models; closure properties; comparison with other language-defining formal devices; erasing operation; erasing system; jumping finite automata; new areas of research; open problems; regulated grammars and automata; aplikace formálních modelů; nové oblasti výzkumu; operace vymazání; otevřené problémy; regulované gramatiky a automaty; skákající konečné automaty; srovnání s jinými formálními zařízeními definujícími jazyk; uzávěrové vlastnosti; vymazávací systém

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/211033

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


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