20.500.12556/RUL-184065 Monadična logika drugega reda in prepoznavni jeziki delo diplomskega seminarja Monadic second order logic and recognisable languages V diplomskem delu dokažemo povezavo med prepoznavnimi jeziki in monadično logiko drugega reda nad signaturo naslednika $\textbf{MSO}[\mathcal{L}_S]$. Uvedemo osnovne pojme iz teorije formalnih jezikov, regularnih izrazov in končnih avtomatov, ter predstavimo monadično logiko drugega reda in njeno interpretacijo na besedah. Kleenejev izrek, ki ga dokažemo z Ardenovo lemo in lastnostmi prepoznavnih in regularnih jezikov, vzpostavi enakost med regularnimi in prepoznavnimi jeziki. Büchijev izrek vzpostavi ekvivalenco med prepoznavnimi jeziki in jeziki, definiranimi v $\textbf{MSO}[\mathcal{L}_S]$. Pri dokazu najprej pokažemo, da vsak prepoznavni jezik lahko opišemo s stavkom monadične logike drugega reda. Nato v obratni smeri vsaki logični formuli s prostimi spremenljivkami priredimo jezik označenih besed nad razširjeno abecedo ter z indukcijo po zgradbi formule dokažemo, da so ti jeziki regularni; regularnost za osnovne formule preverimo neposredno, za logične veznike in kvantifikatorje pa uporabimo zaprtost regularnih jezikov za unijo, presek, komplement in homomorfizme. Iz tega sledi, da je vsak jezik, definiran v $\textbf{MSO}[\mathcal{L}_S]$, prepoznaven. S tem je podana popolna karakterizacija prepoznavnih jezikov z logičnimi formulami monadične logike drugega reda, kar predstavlja enega temeljnih rezultatov teorije formalnih jezikov in avtomatov. In this thesis, we establish the connection between recognizable languages and monadic second-order logic over the successor signature, denoted by $\textbf{MSO}[\mathcal{L}_S]$. We introduce the basic concepts of formal language theory, regular expressions and finite automata, and present monadic second-order logic together with its interpretation over words. Using Arden's lemma and the closure properties of recognizable and regular languages, we prove Kleene's theorem, which states that the classes of regular and recognizable languages coincide. Büchi's theorem establishes the equivalence between recognizable languages and the languages definable in $\textbf{MSO}[\mathcal{L}_S]$. In the proof, we first show that every recognizable language can be described by a sentence of monadic second-order logic. Conversely, we associate each formula with free variables with a language of marked words over an extended alphabet and prove, by induction on the structure of the formula, that all such languages are regular. Regularity for atomic formulas is verified directly, while for logical connectives and quantifiers we use the closure of regular languages under union, intersection, complement, and homomorphisms. Hence every language definable in $\textbf{MSO}[\mathcal{L}_S]$ is recognizable. This yields a complete characterization of recognizable languages in terms of formulas of monadic second-order logic, which is one of the fundamental results in the theory of formal languages and automata. regularni jeziki prepoznavni jeziki končni avtomati monadična logika drugega reda Kleenejev izrek Büchijev izrek regular languages recognizable languages finite automata monadic second-order logic Kleene's theorem Büchi's theorem true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2026-06-25 08:15:07 2026-06-25 08:15:18 2026-06-26 08:20:36 0000-00-00 00:00:00 2026 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 510.6:004.43 160516 282789379 21926.pdf 21926.pdf 1 2552C2A9B855237DE16F905B26A9D163 ee202fba0082edc9f926c0b232bcfa96fa39835918f16f47486f8788431a479a 30deb3eb-705d-11f1-9b0d-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=236524 Fakulteta za matematiko in fiziko 0 0 0