Automaten en Berekenbaarheid

Ga naar: navigatie, zoeken

Dit vak wordt gegeven door prof. Demoen. De site van het vak is http://www.cs.kuleuven.be/~bmd/AB/index2008.html, en daar kan je ook mogelijke examenvragen vinden.

Informatie over het examen

Het examen is volledig mondeling, met schriftelijke voorbereiding. De theorie is gesloten boek, de oefening zijn open boek maar je mag geen opgeloste oefeningen meebrengen (alhoewel je de cursus 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

Hoewel je de vragen schriftelijk mag voorbereiden, is de voorbereiding niet van tel: prof. Demoen werpt geen enkele blik op wat je hebt opgeschreven. Je moet al je antwoorden dus volledig mondeling uitleggen, wat niet gemakkelijk is, omdat de zaken soms nogal abstract zijn en eenvoudig in symbolen op te schrijven zijn, maar moeilijk in woorden te vatten. Prof. Demoen durft je stevig uit te vragen en stelt pittige bijvragen. Zorg dus zeker dat je alles goed mondeling kan uitleggen.

De meeste punten liggen bij de theorievragen (2/3 of 3/4), dit is dus wel degelijk heel belangrijk.

Het gedeelte over Lambda-calculus zat vroeger bij Fundamenten van de Informatica in het eerste jaar, dat toen ook door Bart Demoen werd gegeven. Hiervoor verspreidde hij een lijst van theorievragen. Hoofdstuk 4 van deze cursus komt overeen met het lambda-calculusgedeelte van A&B.

Je hebt anderhalf uur voor de theorie (gesloten boek!), daarna kwartier verdedigen van de theorie, daarna nog 1 uur open boek. In het eerste deel kan je ook al aan de oefening werken, maar dan zonder boek.

Examens

2009

23 januari (namiddag)

  • Definieer de enumerator machine. Bewijs dat elke herkenbare taal kan ge-enumereerd worden en dat elke taal die door een enumerator wordt ge-enumereerd ook herkenbaar is. Kan elke beslisbare taal ge-enumereerd worden? Bespreek in deze context de uitspraak "de verzameling van Turing machines is een herkenbare taal".
  • Bewijs dat een eindige toestandsautomaat altijd een taal herkent die door een reguliere expressie wordt beschreven. Doe dat door een eindige toestandsautomaat te transformeren naar een gegeneraliseerde niet-deterministische eindige toestandsautomaat met slechts twee toestanden.
  • OEFENING: Gegeven een taal L over een alfabet waarin # niet zit en enkel niet-lege strings van een even lengte bevat. Construeer nu de taal gom(L) die (informeel gesproken) de strings uit L bevat maar waarbij in elke string de tekens op de even plaatsen vervangen zijn door #. Formeler: .

Bijvoorbeeld: als dan is . Bewijs (of geen een tegenvoorbeeld van): als L regulier is, dan is gom(L) regulier.

23 januari

  • Wat zijn orakelmachines? Is de verzameling orakelmachines krachtiger dan de verzameling Turing Machines (wat bedoel je met krachtiger?)? Kan je met een orakelmachine met een gegeven orakel alle talen beslissen?
  • Geef de definitie van een PDA. Hoe kan je vanuit een gegeven CFG een PDA construeren? Argumentatie over correctheid van het algoritme.
  • oefening: Bewijs dat de outputtaal van een transducer regulier is (outputtaal: gegeven een inputalfabet S, alle strings die gegenereerd worden door een string in S). Als je strings geeft die niet tot de taal behoren, is de bekomen outputtaal dan nog regulier?

12 januari

  • Geef de definitie van een Myhill-Nerode relatie over een taal L. Bewijs dat een MN(L)-relatie bestaat als en slechts als L regulier is. Bestaat er voor een taal L soms meer dan één MN(L)-relatie?
  • Bewijs dat niet beslisbaar is, zonder op de stelling van Rice te steunen. Zou het helpen als je de stelling van Rice wel zou mogen gebruiken? Is herkenbaar? Co-herkenbaar? Bestaan er talen die noch herkenbaar noch co-herkenbaar zijn? Heb je een voorbeeld?
  • Als en regulier zijn, bewijs dat regulier is (zelfde oefening als 31/1/2008).

2008

14 januari

  • Reconstrueer de details van het verhaal van Myhill-Nerode: elke DFA bepaalt een Myhill-Neroderelatie; elke Myhill-Neroderelatie bepaalt een DFA; twee isomorfe DFA's bepalen dezelfde Myhill-Nerode-relatie; het supremum van twee Myhill-Neroderelaties is een Myhill-Neroderelatie.
    Argumenteer ook het verband tussen de minimale DFA voor een reguliere taal L en de grofste MN(L)-relatie.
    Mondelingen bijvraag: Kan je ook een Myhill-Neroderelatie construeren voor een NFA? Wat krijg je dan met minimalisatie?
  • Geef het bewijs van de stelling is niet beslisbaar. Kan (een variante van) de stelling van Rice helpen om dit te bewijzen?
  • Gegeven is een reguliere taal L over (door een NFA, DFA of RE, kies zelf maar). Beschouw nu de volgende talen (voor elke is er 1):
In woorden: de strings van krijg je door van de strings van L de eerste n tekens weg te laten. In het bijzonder is .
Bewijs dat regulier is voor elke n. Doe dat door een constructiemethode te geven voor een DFA (of NFA) die herkent.
Hoe zit het met de talen die je verkijgt door de laatste n tekens van L weg te laten?


21 januari

  • bespreek de overgang van een dfa naar een minimale dfa. Wat is de equivalentie van een DFA en is er een kleinere DFA dan de minimale DFA, en een NFA?
  • orakelmachine (zelfde examenvraag als uit voorbeelden)
  • oefening: Is de taal Langer(L,n) regulier voor alle waarbij L een reguliere taal is en Langer(L,n) de strings van de taal L zijn die langer zijn dan lengte n.

31 januari

  • Bespreek overgang van NFA naar equivalent DFA. Wat betekent "equivalente machines"? Is deze transformatie deterministisch? Werkt deze transformatie ook om van een NPDA naar een DPDA te gaan?
  • Bewijs dat niet beslisbaar is, zonder Rice. Zou het helpen als je de stelling van Rice mocht gebruiken? Is herkenbaar? Co-herkenbaar? Bestaan er talen die zowel niet-herkenbaar als niet-co-herkenbaar zijn? Voorbeeld?
  • Neem twee strings en over hetzelfde alfabet. Je kan een verzameling van nieuwe strings definieren door de strings te mengen, waarbij de tekens in dezelfde volgorde blijven staan maar niet noodzakelijk meer bij elkaar, bijvoorbeeld . Het is ook mogelijk 2 talen te mengen: . Gegeven twee reguliere talen en , bewijs dat ook regulier is. Bijvraag: als je 2 CFLs mengt, krijg je dan opnieuw een CFL?

2007

15 januari (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.

15 januari (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 . Alle strings in de rest van de opgave zijn elementen van . Definiëer de afstand d(s,t) tussen de strings en als volgt: als . Definiëer nu de taal L1fout = . Bewijs nu het volgende: als L regulier is, dan is L1fout ook regulier. (Hint: vertrek van een DFA van L, en construeer een NFA met toestanden )

18 januari (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

  • 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.


Lijst van examenvragen

Gebruik deze lijst verstandig en voorzichtig. Geen enkele poging werd gedaan om een volledige lijst op te stellen of om alle topics uit de cursus te bedekken. Er is ook geen garantie dat de vragen uit deze lijst effectief zullen gesteld worden op het examen.

  • Geef een preciese formulering van het pompend lemma voor reguliere talen en een bewijs ervan. Geef voorbeelden waarbij je laat zien hoe je dat lemma gebruikt om te bewijzen dat een gegeven taal regulier is en om te bewijzen dat een gegeven taal niet regulier is.
  • Geef een preciese formulering van het pompend lemma voor context-vrije talen en een bewijs ervan. Geef voorbeelden waarbij je laat zien hoe je dat lemma gebruikt om te bewijzen dat een gegeven taal context-vrij is en om te bewijzen dat een gegeven taal niet context-vrij is.
  • 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)
  • 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 geen kleinere equivalente deterministische eindige toestandsautomaat bestaat. Kan een kleinere equivalent niet-deterministische eindige toestandsautomaat bestaan ?
  • Bewijs dat een eindige toestandsautomaat altijd een taal herkent die door een reguliere expressie wordt beschreven. Doe dat door een eindige toestandsautomaat te transformeren naar een gegeneraliseerde niet-deterministische eindige toestandsautomaat met slechts 2 toestanden.
  • Bespreek unie, doorsnede, complement, concatenatie van reguliere talen, van contextvrije talen en van niet-contextvrije talen: zijn die operaties inwendig ? Geef voldoende detail in je argumentatie, eventueel voorbeelden indien nuttig.
  • Definieer de Chomsky Normaal Vorm voor CFGs. Geef de opeenvolgende stappen in het algoritme om een CFG naar een equivalente Chomsky NF te transformeren. Beschrijf de notie van "equivalentie van automaten" in deze context en argumenteer waarom de transformatie "correct" is. Waarvoor is de Chomsky Normaal Vorm nuttig ?
  • Leg uit wat een pushdown automaat is en hoe die werkt. Laat de constructie zien (in het algemeen) van een pushdown automaat die een gegeven contextvrije taal aanvaardt. Argumenteer de correctheid.
  • Leg uit wat een pushdown automaat is en hoe die werkt. Laat de constructie zien (in het algemeen) van een CFG die dezelfde taal genereert als een gegeven pushdown automaat. Argumenteer de correctheid.
  • Geef de definities van "een taal wordt beslist door een Turing machine" en van "een taal wordt herkend door een Turing machine". Bewijs dat er een niet-beslisbare taal bestaat, gebaseerd op een cardinaliteitsargument.
  • Definieer de enumerator machine. Bewijs dat elke herkenbare taal kan ge-enumereerd worden en dat elke taal die door een enumerator wordt ge-enumereerd ook herkenbaar is. Kan elke beslisbare taal ge-enumereerd worden ? Bespreek in deze context de uitspraak "de verzameling van Turing machines is een herkenbare taal".
  • Bewijs in detail dat A_TM niet beslisbaar is - steun daarbij niet op de stelling van Rice. Zou het helpen als het toegelaten was op de stelling van Rice te steunen. Is A_TM herkenbaar ?
  • Formuleer en bewijs in detail de stelling van Rice. Geef voorbeelden van wanneer ze mag toegepast worden en wanneer niet - met argumentie natuurlijk.
  • Wat is een orakelmachine. Bespreek de uitspraak: "de verzameling orakelmachines (voor een gegeven orakel) is strikt krachtiger dan de verzameling van Turing machines". Leg hierbij ook uit wat je bedoelt met "krachtiger". Kan een verzameling orakelmachines (voor bepaald gegeven orakel) alle talen beslissen ?
  • Formuleer en bespreek de stellingen van Church-Rosser. Geef daarbij hun belang i.v.m. het het baseren van een programmeertaal op lambda-calculus. Geef de relatie met de programmeertaal Haskell.
  • Bespreek de Turing-volledigheid van Hornclauselogica. In dezelfde context: bespreek "subsets" van Hornclauselogica die al dan niet Turing-volledig zijn. Geef de relatie met (zuivere) Prolog.