20.500.12556/RUL-129078 Prepoznavnost: končni avtomati in racionalni jeziki delo diplomskega seminarja Recognition: finite automata and rational languages 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. 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. beseda jezik končni avtomat racionalen jezik regularen izraz prepoznaven jezik Kleenijev izrek word language finite automaton rational language regular expression recognizable language Kleene theorem true false false Slovenski jezik Angleški jezik Delo diplomskega seminarja/zaključno seminarsko delo/naloga 2021-08-26 08:15:02 2021-08-26 08:15:06 2024-05-29 14:01:23 0000-00-00 00:00:00 2021 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.7 118894 74264835 3034.pdf 3034.pdf 1 7018B916708550AC7AFBD01B968CD2F3 3b55a227a13ac70734e53d8758a4e6cec987e84d7eeb887f1f31e0fac6e60434 bc8b7cbb-0634-11ec-a523-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=146004 Fakulteta za matematiko in fiziko 0 0 0