eksamid
Kool: Tartu Ülikool (TÜ)
Aine: Teoreetiline informaatika
Kategooria: Informaatika
Postitatud: 7 jaanuar 2025
Postitaja: HellGorilla
Kirjeldus
Sissejuhatus teoreetilisse informaatikasse Sgis 2016 19. detsembri eksami lahendused 1. Deneerime keele L1 A A on deterministlik lplik automaat ja A keel on (010)n n 1. Nita et L1 on lahenduv keel. Juhis ks vimalik viis seda lesannet lahendada on kasutada fakti et Lon lahenduv keel (nidatud loengus) kus L A A on deterministlik lplik automaat ja L(A) . Vaatleme deterministlikku lplikku automaati B mis aktsepteerib kiki s- nesid vlja arvatud sned kujul (010)n n 1. Lahendus. Vaatleme hoopis deterministilikku lplikku automaati C mis akt- septeerib kiki snesid kujul (010)n n 1. See automaat on olemas sest nende snede hulka esitab regulaaravaldis (010) ning regulaaravaldisega kir- jeldatav keel on regulaarne. Kirjeldame Turingi masinat M1 mis lahendab keelt L1. See masin tegut- seb sisendil Ajrgmiselt. 1. Konstrueerib deterministliku lpliku automaadi D mille puhul L(D) (L(A)L(C))(L(A)L(C)). See automaat on sisendautomaadi A ja konstantse automaadi C jrgi algoritmiliselt konstrueeritav (…