Monadična logika drugega reda in prepoznavni jezikiNemanič, Anara (Avtor) Kudryavtseva, Ganna (Mentor) regularni jezikiprepoznavni jezikikončni avtomatimonadična logika drugega redaKleenejev izrekBüchijev izrekV 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.20262026-06-25 08:15:07Diplomsko delo/naloga184065sl