Název:
Regulované jazykové operace a jejich užití
Překlad názvu:
Regulated Language Operations and Their Use
Autoři:
Chocholatý, David ; Kožár, Tomáš (oponent) ; Meduna, Alexandr (vedoucí práce) Typ dokumentu: Bakalářské práce
Rok:
2023
Jazyk:
cze
Nakladatel: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstrakt: [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.
Klíčová slova:
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; 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
Instituce: Vysoké učení technické v Brně
(web)
Informace o dostupnosti dokumentu:
Plný text je dostupný v Digitální knihovně VUT. Původní záznam: http://hdl.handle.net/11012/211033