Prepoznavnost
končni avtomati in racionalni jeziki
Povzetek
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.
Ključne besede
teorija formalnih jezikov;besede;jeziki;končni avtomati;racionalni jeziki;regularni izrazi;prepoznavni jeziki;Kleenijev izrek;
Podatki
| Jezik: | Slovenski jezik |
|---|---|
| Leto izida: | 2021 |
| Tipologija: | 2.11 - Diplomsko delo |
| Organizacija: | UL FGG - Fakulteta za gradbeništvo in geodezijo |
| Založnik: | [K. Draksler] |
| UDK: | 519.765 |
| COBISS: |
74264835
|
| Št. ogledov: | 680 |
| Št. prenosov: | 55 |
| Ocena: | 0 (0 glasov) |
| Metapodatki: |
|
Ostali podatki
| Sekundarni jezik: | Angleški jezik |
|---|---|
| Sekundarni naslov: | Recognition: finite automata and rational languages |
| Sekundarni povzetek: | 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. |
| Sekundarne ključne besede: | formal language theory;words;languages;finite automaton;rational languages;regular expressions;recognizable languages;Kleene theorem; |
| Vrsta dela (COBISS): | Delo diplomskega seminarja/zaključno seminarsko delo/naloga |
| Študijski program: | 0 |
| Komentar na gradivo: | Univ. v Ljubljani, Fak. za matematiko in fiziko, Oddelek za matematiko, Matematika - 1. stopnja |
| Strani: | 26 str. |
| ID: | 13282192 |
Priporočena dela: