Automaten en Berekenbaarheid

Dit vak wordt gegeven door prof. Demoen.

Informatie over het examen

Het examen is volledig mondeling, met schriftelijke voorbereiding. De theorie is gesloten boek, de oefening is open boek (alhoewel je het boek eigenlijk niet nodig hebt)

• Vraag 1: een 'makkelijke' theorievraag, uit het lijstje van de mogelijke examenvragen
• Vraag 2: een 'moeilijke' theorievraag, ook ergens uit de cursus
• Vraag 3 (open boek): oefening waarin je iets moet bewijzen

Examens

2007-01-15 (voormiddag)

• Geef het pumping lemma voor cfg's. Gebruik het om te bewijzen dat een taal wel (tricky) en een taal niet cf is.
• Zijn alle cfg's deterministisch? Bewijs waarom wel/niet. Het antwoord is dat bewijs op een apart blad waarin deterministische automaat voor {XiYiZi} wordt gemaakt, wat niet kan.
• Er zijn 2 reguliere talen. Is de doorsnede van de ene taal met de reverse van de andere taal ook regulier? bewijs.

2007-01-15 (namiddag)

• Beschrijf in detail de transformatie van een deterministische eindige toestandsautomaat naar een equivalente deterministische eindige toestandsautomaat met een minimaal aantal toestanden. Beschrijf de notie van "equivalentie van automaten" in deze context en argumenteer waarom er wel of geen kleinere equivalente deterministische eindige toestandsautomaat bestaat. Kan een kleinere equivalent niet-deterministische eindige toestandsautomaat bestaan?
• Beschrijf het correspondentieprobleem van Post. Argumenteer waarom het onbeslisbaar is. Is het herkenbaar? argumenteer
• Stel L een taal met $|\mathrm{\Sigma }|\ge 2$. Alle strings in de rest van de opgave zijn elementen van ${\mathrm{\Sigma }}^{*}$. Definiëer de afstand d(s,t) tussen de strings $s=s_0{s}_1\dots s_n$ en $t=t_0{t}_1\dots t_n$ als volgt: $d(s,t)=\mathrm{♯}\{i|s_i\ne t_i\}$ als $|s|=|t|$. Definiëer nu de taal L₁fout = $\{x|\mathrm{\exists }a\in L:|a|=|x|\wedge d(a,x)\le 1\}$. Bewijs nu het volgende: als L regulier is, dan is L₁fout ook regulier. (Hint: vertrek van een DFA van L, en construeer een NFA met toestanden $Q\times \{0,1\}$)

2007-01-18 (voormiddag)

• enumerator machine: beschrijven, bewijzen dat herkenbare talen door enumerator ge-enumereert kunnen worden, en dat ge-enumereerde talen herkenbaar zijn. Zijn turing machines enumereerbaar? herkenbaar? Beslisbaar of <M> de beschrijving van een turing machine is.

• bewijs in detail of REGULAR(TM) besisbaar is. Is het herkenbaar? Is het complement herkenbaar?

• moeilijke oefening

25 januari 2007

Voormiddag Michaël:

• Beschrijf in detail de transformatie van een niet-deterministische

eindige toestandsautomaat naar een equivalente deterministische eindige toestandsautomaat. Beschrijf de notie van "equivalentie van automaten" in deze context en argumenteer waarom de transformatie "correct" is. Bespreek de uitspraak "deze transformatie is [niet] deterministisch". (kies zelf of je die "niet" wil houden of niet)

• Bewijs dat E(tm) niet beslisbaar is. Is E(tm) herkenbaar? co-herkenbaar?

bijvraag: kan je de stelling van rice gebruiken?

• Gegeven: Taal L over alfabet Epsilon1 x Epsilon2. Zij P1 en P2 beide projecties van L naar een taal op Epsilon1 respectievelijk Epsilon 2. Voor P1 geldt P1 = {a|a = a1a2a3...an, Er bestaat een w € L zodat w = (a1,x1)(a2,x2)...(an,xn)}

Is P1 regulier? (Toon aan door DFA te schrijven of een tegenvoorbeeld te geven. Helpt het als gegeven wordt dat P2 regulier is? (Je kan een hint vragen in ruil voor een paar punten)

Hint was: beschouw een transactie van twee toestanden met daarin (ai,xi) als label op de pijl. Dan kan je deze transactie voor de machine P1 voorstellen als dezelfde toestanden maar dan met label ai. Deze automaat is wel een NDFA, want bv voor d(q0,(a,b)) = q1 en d(q0,(a,c)) = q2 krijg je d(q0,a) = {q1,q2} en dat is niet deterministisch. Je moet nu nog bewijzen dat voor een string s die geaccepteerd word door P1 dus s = s1s2s3...sn met si € Epsilon 1 dat er een element (s1,b1)(s2,b2)...(sn,bn) bestaat in L. Dit kan je doen door elke keer een string te kiezen uit Epsilon2^n en die uit te proberen samen met s1 op de machine van L. Ooit kom je wel een juiste string tegen want Epsilon^ster is aftelbaar.