Prepoznavnost

končni avtomati in racionalni jeziki

Katja Draksler (Author), Ganna Kudryavtseva (Mentor)

Abstract

V diplomski nalogi se seznanimo s teorijo formalnih jezikov, kjer obravnavamo jezike in operacije na njih. Definiramo končne avtomate, spoznamo njihove lastnosti in obravnavamo njihovo zvezo z besedami in jeziki. Prek končnih avtomatov definiramo prepoznavne jezike in jih povežemo s posebnim razredom jezikov, imenovanih racionalni jeziki. Ta pomemben rezultat imenovan Kleenijev izrek v delu formuliramo in podamo njegov dokaz. Seznanimo se z linearnimi enačbami in sistemi linearnih enačb definiranih na jezikih. Določimo pogoje pod katerimi ima enačba oziroma sistem enačb enolično rešitev. Pri tem rezultatu sta pomembna Ardenova lema in njen dokaz. Prikažemo postopek, ki končnemu avtomatu vrne pripadajoč racionalen jezik.

Keywords

teorija formalnih jezikov;besede;jeziki;končni avtomati;racionalni jeziki;regularni izrazi;prepoznavni jeziki;Kleenijev izrek;

Data

Language:	Slovenian
Year of publishing:	2021
Typology:	2.11 - Undergraduate Thesis
Organization:	UL FGG - Faculty of Civil and Geodetic Engineering
Publisher:	[K. Draksler]
UDC:	519.765
COBISS:	74264835
Views:	680
Downloads:	55
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Recognition: finite automata and rational languages
Secondary abstract:	In the diploma thesis, we deal with the formal language theory, where we discuss languages and operations on them. We define finite automata, learn their properties and address their relationship to words and languages. Through finite automata we define recognizable languages and connect them to the special class of languages called rational languages. In the work, we formulate Kleene’s theorem and give its proof. We introduce linear equations and systems of linear equations defined on languages. We determine conditions under which an equation or a system of equations has a unique solution. Arden's lemma and its proof are important in this result. We provide the algorithm that returns the corresponding rational language to a given finite automaton.
Secondary keywords:	formal language theory;words;languages;finite automaton;rational languages;regular expressions;recognizable languages;Kleene theorem;
Type (COBISS):	Final seminar paper
Study programme:	0
Thesis comment:	Univ. v Ljubljani, Fak. za matematiko in fiziko, Oddelek za matematiko, Matematika - 1. stopnja
Pages:	26 str.
ID:	13282192