Automaten en Berekenbaarheid

Ga naar: navigatie, zoeken
BartDemoen.jpg

Inhoud

Lesnota's en oefenzittingen

Klik hier om de lesnota's en/of oefenzittingen te bekijken

- Notities van Syd

Samenvattingen

Klik hier om de samenvattingen te bekijken

- Samenvatting inclusief opgeloste examenvragen

- Samenvatting Jonas Soenen (2016-2017): READ ME HF2 HF3 HF4

Vakinformatie

Academiejaar 2018-2019

Het vak werd dit jaar overgenomen door prof. Denecker. De examenvragen en oefenzittingen zijn nog steeds op de site vinden, maar deze is nu verhuisd naar https://people.cs.kuleuven.be/~marc.denecker/AB/. Op de site vind je daarnaast ook enkele korte video's van prof. Demoen die als voorbereiding voor de hoorcolleges dienen. De inhoud, tussentijdse testen en examenvorm en -vragen van het vak zijn hetzelfde gebleven. Prof. Denecker kijkt wel naar je voorbereiding op het mondeling examen.

Het vak voor 2018-2019

Dit vak wordt gegeven door prof. Demoen. De site van het vak is http://people.cs.kuleuven.be/~bart.demoen/AB/index.html, en daar kan je ook mogelijke examenvragen vinden. Het examen is volledig mondeling en gesloten-boek, met schriftelijke voorbereiding. Er worden telkens 2 theorievragen gesteld uit de cursus, je krijgt een uur voor de voorbereiding en een kwartier voor de verdediging.

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. Vorige jaren waren er ook oefeningenvragen op het examen, sinds 2012 wordt dit niet meer gedaan.

Na elke helft van het semester is er een gequoteerde oefenzitting (of tenminste vanaf het academiejaar 2015-2016). Deze staan elk op 3 van de 20 punten voor het vak en volgen het model van een schriftelijk open-boek examen, je krijgt 1u30 en mag de cursus gebruiken (maar geen oude examenvragen, opgeloste oefeningen, aanwijzingen tot oplossingen, ...). Dit is echter niet zo belangrijk, je wordt er namelijk op getest of je (snel genoeg) de theorie kan toepassen op allerlei manieren. De vragen zijn van een pak hoger niveau dan die uit de oefenzittingen, dus zorg dat je genoeg oefeningen maakt om deze voor te bereiden, soms is er grote tijdsdruk en kan het erg helpen om bepaalde veel-voorkomende constructies van buiten te kennen (bv. tegenvoorbeelden van talen die wel/niet regulier/context-vrij zijn, ...). Bovendien worden sommige vragen hergebruikt. Zie hieronder voor voorbeelden.

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.

Gequoteerde oefenzittingen

December 2018

Tweede gequoteerde oefenzitting 2018

Oktober 2018

Eerste gequoteerde oefenzitting 2018

Oktober 2017

Eerste gequoteerde oefenzitting 2017

December 2016

Media:AB_gekwot2_dec_2016.pdf

November 2016

Media:AB_gekwot1_nov_2016.pdf

December 2015

Media:December2015.pdf

December 2014

Media:December2014.pdf

November 2014

Media:Gequoteerde_oefenzitting_november_2014_(opgelost).pdf

December 2013

Media:Gequoteerde_oefenzitting_december_2013_(opgelost).pdf

November 2013

Media:Gequoteerde_oefenzitting_november_2013_(opgelost).pdf

Examenvragen

2019

25 januari 2019, Namiddag I

  • 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 de stelling van Rice uit, en geef het bewijs. Geef minstens één eigenschap van Turingmachines die niet voldoet aan de voorwaarde voor de stelling van Rice, en laat zien dat die eigenschap geen aanleiding geeft tot een niet-beslisbare taal.
    • Bijvraag: voor een verzameling S van talen kan men definieren:

{<M> | L_{M} S}. Kan je alle eigenschappen van Turingmachines die aan de stelling van Rice voldoen m.b.v. karakteriseren?

25 januari 2019, Voormiddag II

  • 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.
  • Geef een precieze 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.
    • Bijvraag: Is er een verband tussen de kleinste DFA voor een taal en de kortste pomplengte?

24 januari 2019, Voormiddag II

  • Geef de definitie van een Myhill-Nerode relatie over een taal L, of zoals we noteren een -relatie. Bewijs vervolgens dat een -relatie bestaat als en slechts als L regulier is. Bestaat er voor een taal L soms meer dan één relatie?
  • 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)

24 januari 2019, Voormiddag I

  • Beschrijf in detail de transformatie van een DFA naar een equivalente DFA met een minimaal aantal toestanden. Beschrijf de notie van equivalentie van automaten in deze context en argumenteer waarom er geen kleinere equivalente DFA bestaat. Bijvraag: kan een kleinere NFA bestaan?
  • Bewijs in detail dat 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 herkenbaar? Co-herkenbaar?

23 januari 2019, Voormiddag I

  • Geef de opbouw van de primitief recursieve functies, en die van de recursieve functies. Argumenteer waarom al die functies met een Turingmachine kunnen berekend worden, en omgekeerd. Is er een verband tussen de berekenbaarheid van een functie en de grootte van zijn domein en/of bereik?
  • Geef informeel de definitie van een lineair begrensde automaat (LBA). Argumenteer dat het aanvaardingsprobleem voor LBA's () beslisbaar is. Geef de stappen in een bewijs dat (de verzameling LBA's die de lege taal bepalen) niet beslisbaar is.

22 januari 2019, Voormiddag II

  • Geef een precieze 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.
  • 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".
    • Bijvraag: stel dat je van een taal L een enumerator hebt die string van L produceert in volgorde van grootte. Is L herkenbaar? Is L besisbaar?

22 januari 2019, Voormiddag I

  • Formuleer en bespreek de stellingen van Church-Rosser. Geef daarbij hun belang i.v.m. het baseren van een programmeertaal op lambda-calculus. Geef de relatie met de programmeertaal Haskell.
  • Geef het bewijs van de stelling is niet beslisbaar: doe dat zonder de stelling van Rice te gebruiken. Bespreek daarna de uitspraken is herkenbaar en is co- herkenbaar. (De E staat voor Empty) Ken je ook alternatieve bewijzen? Hoe zit het met ?

2018

26 januari 2018, Namiddag II

  • Formuleer en bespreek de stellingen van Church-Rosser. Geef daarbij hun belang i.v.m. het baseren van een programmeertaal op lambda-calculus. Geef de relatie met de programmeertaal Haskell.
  • Geef het bewijs van de stelling is niet beslisbaar: doe dat zonder de stelling van Rice te gebruiken. Bespreek daarna de uitspraken is herkenbaar en is co- herkenbaar. (De E staat voor Empty) Ken je ook alternatieve bewijzen? Hoe zit het met ?

25 januari 2018, Namiddag II

  • Beschrijf in detail de transformatie van een DFA naar een equivalente DFA met een minimaal aantal toestanden. Beschrijf de notie van equivalentie van automaten in deze context en argumenteer waarom er geen kleinere equivalente DFA bestaat. Bijvraag: kan een kleinere NFA bestaan?
  • Bewijs in detail dat 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 herkenbaar? Co-herkenbaar?

25 januari 2018, Voormiddag I

  • Geef de definitie van een Myhill-Nerode relatie over een taal L, of zoals we noteren een -relatie. Bewijs vervolgens dat een -relatie bestaat als en slechts als L regulier is. Bestaat er voor een taal L soms meer dan één relatie?
  • Leg de stelling van Rice uit, en geef het bewijs. Geef minstens één eigenschap van Turingmachines die niet voldoet aan de voorwaarde voor de stelling van Rice, en laat zien dat die eigenschap geen aanleiding geeft tot een niet-beslisbare taal.
    • Bijvraag: voor een verzameling S van talen kan men definieren:

{<M> | L_{M} S}. Kan je alle eigenschappen van Turingmachines die aan de stelling van Rice voldoen m.b.v. karakteriseren?

24 januari 2018, Voormiddag I

  • Geef de definitie van een PDA. Leg de werking uit. Geef de algemene opbouw van een PDA die een bepaalde CFG bepaalt.
    • Bijvraag: Is de doorsnede tussen het stackalfabet en het invoeralfabet leeg? Zou dit een verschil maken voor de kracht van de PDA?
  • Bespreek de stellingen van Church-Rosser. Wat betekent dit voor het gebruik van de lambda-calculus als programmeertaal? Geef het verband met Haskell.

2017

27 januari 2017, Namiddag

  • Geef de opbouw van de primitief recursieve functies, en die van de recursieve functies. Argumenteer waarom al die functies met een Turingmachine kunnen berekend worden, en omgekeerd. Is er een verband tussen de berekenbaarheid van een functie en de grootte van zijn domein en/of bereik?
  • Geef informeel de definitie van een lineair begrensde automaat (LBA). Argumenteer dat het aanvaardingsprobleem voor LBA's () beslisbaar is. Geef de stappen in een bewijs dat (de verzameling LBA's die de lege taal bepalen) niet beslisbaar is.

27 januari 2017, Voormiddag I

  • Geef de definitie van een Myhill-Nerode relatie over een taal L, of zoals we noteren een -relatie. Bewijs vervolgens dat een -relatie bestaat als en slechts als L regulier is. Bestaat er voor een taal L soms meer dan één -relatie?
    • Bijvraag: Bestaan er voor elke reguliere taal oneindig veel relaties?
  • Bespreek de twee noties van reduceerbaarheid ( en ), hun verband en op welke manier die noties kunnen gebruikt worden om aan te tonen dat een taal (on)beslisbaar/herkenbaar is.
    • Bijvraag: als , kan je dan ook het complement van A reduceren naar B, A reduceren naar het complement van B, het complement van A reduceren naar het complement van B (allemaal Turing-reducties)?
    • Bijvraag: kan je elke beslisbare taal many-to-one reduceren naar een gegeven reguliere taal? Indien ja, betekent dit dan dat je elke CFL kan many-to-one reduceren tot een reguliere taal?

26 januari 2017, Voormiddag I

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

25 januari 2017, Voormiddag I

  • Geef een precieze 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.
  • 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".

25 januari 2017, Voormiddag II

  • Geef de definitie van een Myhill-Nerode relatie over een taal L, of zoals we noteren een -relatie. Bewijs vervolgens dat een -relatie bestaat als en slechts als L regulier is. Bestaat er voor een taal L soms meer dan één relatie?
  • Leg de stelling van Rice uit, en geef het bewijs. Geef minstens één eigenschap van Turingmachines die niet voldoet aan de voorwaarde voor de stelling van Rice, en laat zien dat die eigenschap geen aanleiding geeft tot een niet-beslisbare taal.
    • Bijvraag: voor een verzameling S van talen kan men definieren:

{<M> | L_{M} S}. Kan je alle eigenschappen van Turingmachines die aan de stelling van Rice voldoen m.b.v. karakteriseren?

25 januari 2017, Namiddag I

  • Beschrijf in detail de transformatie van een deterministische eindige toestandsautomaat naar een equivalente determinischtische 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 einde toestandsautomaat bestaat. Bijvraag: Kan een kleinere equivalente niet-deterministische einde toestandsautomaat bestaan?
  • Bewijs in detail dat 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 herkenbaar? co-herkenbaar?

2016

20 januari 2016 Voormiddag I

  • Geef de definitie van een Myhil-Nerode relatie over een taal L, of zoals we noteren een -relatie. Bewijs vervolgens dat een -relatie bestaat als en slechts als L regulier is. Bestaat er voor een taal L soms meer dan één relatie?
  • Leg de stelling van Rice uit, en geef het bewijs. Geef minstens één eigenschap van Turingmachines die niet voldoet aan de voorwaarde voor de stelling van Rice, en laat zien dat die eigenschap geen aanleiding geeft tot een niet-beslisbare taal. Bijvraag maar anders geformuleerd: Karakteriseer volledig alle eigenschappen van Turingmachines die aan de stelling van Rice voldoen m.b.v. .

20 januari 2016 Namiddag I

  • Beschrijf in detail de transformatie van een deterministische eindige toestandsautomaat naar een equivalente determinischtische 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 einde toestandsautomaat bestaat. Bijvraag: Kan een kleinere equivalente niet-deterministische einde toestandsautomaat bestaan?
  • Bewijs in detail dat 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 herkenbaar? co-herkenbaar?

20 januari 2016 Namiddag II

  • Beschrijf in detail de transformatie van een deterministische eindige toestandsautomaat naar een equivalente determinischtische 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 einde toestandsautomaat bestaat. Bijvraag: Kan een kleinere equivalente niet-deterministische einde toestandsautomaat bestaan?
  • Leg de stelling van Rice uit, en geef het bewijs. Geef minstens één eigenschap van Turingmachines die niet voldoet aan de voorwaarde voor de stelling van Rice, en laat zien dat die eigenschap geen aanleiding geeft tot een niet-beslisbare taal. Bijvraag maar anders geformuleerd: Karakteriseer volledig alle eigenschappen van Turingmachines die aan de stelling van Rice voldoen m.b.v. .

21 januari 2016 Namiddag I

  • Geef het algoritme om een CFG naar zijn PDA om te zetten en bewijs de correctheid hiervan.
    • Bijvraag: Volgens een constructie in de cursus worden meerdere elementen per keer gepushed, waarom mag dit?
  • Leg de stelling van Rice uit, en geef het bewijs. Geef minstens één eigenschap van Turingmachines die niet voldoet aan de voorwaarde voor de stelling van Rice, en laat zien dat die eigenschap geen aanleiding geeft tot een niet-beslisbare taal. Bijvraag maar anders geformuleerd: Karakteriseer volledig alle eigenschappen van Turingmachines die aan de stelling van Rice voldoen m.b.v. .

21 januari 2016 Namiddag II

  • Geef de definitie van een Myhil-Nerode relatie over een taal L, of zoals we noteren een -relatie. Bewijs vervolgens dat een -relatie bestaat als en slechts als L regulier is. Bestaat er voor een taal L soms meer dan één relatie?
  • 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.

22 januari 2016 Namiddag I

  • Formuleer en bespreek de stellingen van Church-Rosser. Geef daarbij hun belang i.v.m. het baseren van een programmeertaal op lambda-calculus. Geef de relatie met de programmeertaal Haskell.
    • Bijvraag: Is λ-calculus Turing-compleet? (Kan een Turingmachine in λ-calculus voorgesteld worden?)
  • Geef het bewijs van de stelling is niet beslisbaar: doe dat zonder de stelling van Rice te gebruiken. Bespreek daarna de uitspraken is herkenbaar en is co-herkenbaar. (de staat voor Empty) Ken je ook alternatieve bewijzen? Hoe zit het met ?

2015

31 augustus 2015 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 geen kleinere equivalente deterministische eindige toestandsautomaat bestaat.
    • Bijvraag: kan een kleinere equivalente niet-deterministische eindige toestandsautomaat bestaan?
  • Bewijs in detail dat 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 herkenbaar? co-herkenbaar?

23 januari 2015 Voormiddag

  • Geef een precieze 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.
  • Bespreek de twee noties van reduceerbaarheid ( en ), hun verband en op welke manier die noties kunnen gebruikt worden om aan te tonen dat een taal (on)beslisbaar/herkenbaar is.

22 januari 2015 Namiddag 1

  • 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.
    • Bijvraag: kan een kleinere equivalente niet-deterministische eindige toestandsautomaat bestaan?
  • 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".

22 januari 2015 Namiddag 2

  • 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.
    • Bijvraag: hoeveel conversieregels ken je?
  • Geef het bewijs van de stelling is niet beslisbaar: doe dat zonder de stelling van Rice te gebruiken. Bespreek daarna de uitspraken is herkenbaar en is co-herkenbaar. (de E staat voor Empty) Ken je ook alternatieve bewijzen? Hoe zit het met ?

21 januari 2015 Namiddag 2

  • Geef de definitie van een Myhil-Nerode relatie over een taal L, of zoals we noteren een MN(L)-relatie. Bewijs vervolgens 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?
  • 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.

21 januari 2015 Namiddag 1

  • Geef het algoritme om een CFG naar zijn PDA om te zetten en bewijs de correctheid hiervan.
    • Bijvraag: Volgens een constructie in de cursus worden meerdere elementen per keer gepushed, waarom mag dit?
  • Leg de stelling van Rice uit, en geef het bewijs. Geef minstens één eigenschap van Turingmachines die niet voldoet aan de voorwaarde voor de stelling van Rice, en laat zien dat die eigenschap geen aanleiding geeft tot een niet-beslisbare taal. Bijvraag maar anders geformuleerd: Karakteriseer volledig alle eigenschappen van Turingmachines die aan de stelling van Rice voldoen m.b.v. .

12 januari 2015 Voormiddag

  • Geef de definitie van een Myhil-Nerode relatie over een taal L, of zoals we noteren een -relatie. Bewijs vervolgens dat een -relatie bestaat als en slechts als L regulier is. Bestaat er voor een taal L soms meer dan één relatie?
  • Leg de stelling van Rice uit, en geef het bewijs. Geef minstens één eigenschap van Turingmachines die niet voldoet aan de voorwaarde voor de stelling van Rice, en laat zien dat die eigenschap geen aanleiding geeft tot een niet-beslisbare taal. Bijvraag maar anders geformuleerd: Karakteriseer volledig alle eigenschappen van Turingmachines die aan de stelling van Rice voldoen m.b.v. .

12 januari 2015 Namiddag

  • Beschrijf in detail de transformatie van een deterministische eindige toestandsautomaat naar een equivalente determinischtische 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 einde toestandsautomaat bestaat. Bijvraag: Kan een kleinere equivalente niet-deterministische einde toestandsautomaat bestaan?
  • Bewijs in detail dat 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 herkenbaar? co-herkenbaar?

2014

24 januari 2014 Namiddag 1

  • Geef de definitie van een Myhil-Nerode relatie over een taal L, of zoals we noteren een MN(L)-relatie. Bewijs vervolgens 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?
  • 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.

24 januari 2014 Voormiddag 1

  • Bewijs dat een reguliere taal beschreven door een reguliere expressie door een eindige toestandsautomaat wordt herkend. Doe dit door van de automaat een gegeneraliseerde niet-deterministische eindige toestandsautomaat te maken. Beschrijf in detail hoe uit die GNFA een reguliere expressie kan worden afgeleid.
    • Bijvragen tijdens mondeling zelf:
      • Kan voor een PDA ongeveer hetzelfde gedaan worden door een gegeneraliseerde PDA op te stellen?
      • Cursus pagina 23 figuur 2.7: Stel dat het linkse deel toestand B niet bevat, de boog met van X naar A en de boog met van A naar zichzelf gaat. Kan dit omgevormd worden op een gelijkaardige manier als de originele manier? Dit kan omgevormd worden naar slechts één boog tussen A en X met als RE:

[(E_4)^*E_1(E_2)^*E_3]^*(E_4)^*E_1(E_2)^*

  • Bewijs dat niet beslisbaar is. Maak hierbij geen gebruik van de stelling van Rice. Mocht dat wel toegestaan zijn, zou de stelling van Rice je dan kunnen helpen? Is herkenbaar?
    • Bijvraag: is co-herkenbaar?

23 januari 2014 Voormiddag 1

  • 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.
    • Bijvraag: kan een kleinere equivalente niet-deterministische eindige toestandsautomaat bestaan?
  • 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".

23 januari 2014 Voormiddag 2

  • 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)
    • Bijvraag: kan er zo'n DFA bestaan met minder toestanden dan de NFA?
  • Wat is een orakelmachine. Bespreek de uitspraak: "de verzameling orakelmachines (over 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?
    • Bijvraag: Kan een orakelmachine voor , beslissen?

13 januari 2014 - Namiddag 1

  • 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.
    • Bijvraag: kan een kleinere equivalente niet-deterministische eindige toestandsautomaat bestaan?
  • Bewijs in detail dat 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 herkenbaar? Co-herkenbaar?

13 januari 2014 - Namiddag 2

  • Geef een precieze 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.
    • Bijvraag: Is er een verband tussen de kleinste DFA voor een taal en de kortste pomplengte?
  • Bespreek de twee noties van reduceerbaarheid ( en ), hun verband en op welke manier die noties kunnen gebruikt worden om aan te tonen dat een taal (on)beslisbaar/herkenbaar is.

13 januari 2014 - Voormiddag 1

  • Geef een precieze 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.
  • Wat is een enumeratormachine? Zijn alle geënumereerde talen herkenbaar? Kan je alle herkenbare talen enumereren? Zijn beslisbare talen enumereerbaar? Is de verzameling van alle TM herkenbaar? Stel dat je voor een taal L een enumerator hebt die de strings van L in volgorde van grootte enumereert, is L dan herkenbaar? Is L dan beslisbaar?

2013

14 januari 2013 - Voormiddag I

  • Geef de definitie van een Myhil-Nerode relatie over een taal L, of zoals we noteren een -relatie. Bewijs vervolgens dat een -relatie bestaat als en slechts als L regulier is. Bestaat er voor een taal L soms meer dan één relatie?
  • Leg de stelling van Rice uit, en geef het bewijs. Geef minstens één eigenschap van Turingmachines die niet voldoet aan de voorwaarde voor de stelling van Rice, en laat zien dat die eigenschap geen aanleiding geeft tot een niet-beslisbare taal. Karakteriseer volledig alle eigenschappen van Turingmachines die aan de stelling van Rice voldoen m.b.v. .

14 januari 2013 - Voormiddag II

  • Wat is een enumeratormachine? Zijn alle geenumereerde talen herkenbaar? Kan je alle herkenbare talen enumereren? Zijn beslisbare talen enumereerbaar? Is de verzameling van alle TM herkenbaar?
  • Vertel alles wat je weet i.v.m. de Chomsky-hierarchie binnen de 5 minuten. Bijvraag: Zijn de talen van een TM beslisbaar en wat is de tijdscomplexiteit was doorheen de Chomsky-hierarchie.

14 januari 2013 - Voormiddag III

  • Geef alle stappen (stellingen & bewijzen) om aan te tonen dat alle minimale DFA's die dezelfde taal bepalen isomorf zijn
  • Geef de conversieregels voor lambda-calculus, bespreek de stellingen van Church-Rosser en leg a.d.h. daarvan uit hoe je een recursieve functie in lambda calculus kunt maken + geef een voorbeeld (niet dat uit de cursus).

18 januari 2013 - Voormiddag

  • Beschrijf in detail de transformatie van een DFA naar een equivalente DFA met een minimaal aantal toestanden. Beschrijf de notie van equivalentie van automaten in deze contect en argumenteer waarom er geen kleinere equivalente deterministische eindige toestandsautomaat bestaat. Kan een kleinere equivalanete NFA bestaan?
  • Geef in 5 minuten zoveel mogelijk relevante informatie over de Chomsky hierarchie. Bijvraag: Zijn de talen van een TM beslisbaar en wat is de tijdscomplexiteit was doorheen de Chomsky-hierarchie.

18 januari 2013 - Namiddag

  • Geef de opeenvolging van stellingen en algoritmen die leiden tot de uitspraak Voor een reguliere taal zijn alle minimale DFA's isomorf. Bereid voor om ook over de bewijzen van de stellingen te praten en/of over de correctheid van de algoritmen.
  • Leg eerst de conversie-regels van lambda-calculus uit en de twee stellingen van Church-Rosser. Laat daarna zien hoe je in zuivere lambda-calculus recursieve functies kan definiëren. Doe dat mbv een voorbeeld recursieve functie verschillend van FAC uit de cursus.

21 januari 2013 - Namiddag

  • 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.
  • Bewijs in detail dat niet beslisbaar is. Bespreek is herkenbaar en is co-herkenbaar.Wat kan je zeggen over ? [Zou kunnen dat er hier nog iets bij werd gevraagd, maar dat weet ik niet meer] Bijvraag: Zou het helpen als het toegelaten was op de stelling van Rice te steunen?

21 januari 2013 - Namiddag

  • Geef de definitie van een Myhill-Nerode relatie over een taal L, of zoals we noteren een -relatie. Bewijs vervolgens dat een -relatie bestaat als en slechts als L regulier is. Bestaat er voor een taal L soms meer dan één -relatie?
  • Bespreek de 2 noties van reduceerbaarheid ( en ), hun verband en op welke manier deze kunnen gebruikt worden om aan te tonen dat talen (on)beslisbaar/herkenbaar zijn.

25 januari 2013 - Namiddag I

  • Leg de stelling van Rice uit, en geef het bewijs. Geef minstens één eigenschap van Turingmachines die niet voldoet aan de voorwaarde voor de stelling van Rice, en laat zien dat die eigenschap geen aanleiding geeft tot een niet-beslisbare taal. Karakteriseer volledig alle eigenschappen van Turingmachines die aan de stelling van Rice voldoen m.b.v. IsInTM,S.
  • Leg eerst de conversie-regels van lambda-calculus uit en de twee stellingen van Church-Rosser. Laat daarna zien hoe je in zuivere lambda-calculus recursieve functies kan definiëren. Doe dat mbv een voorbeeld recursieve functie verschillend van FAC uit de cursus.

25 januari 2013 - Namiddag II

  • Geef in 5 minuten zoveel mogelijk relevante informatie over de Chomsky hierarchie
  • Bespreek de 2 noties van reduceerbaarheid ( en ), hun verband en op welke manier deze kunnen gebruikt worden om aan te tonen dat talen (on)beslisbaar/herkenbaar zijn.

2012

7 september

  • Geef de definitie van een Myhill-Nerode relatie over een taal L, of zoals we noteren een MN(L)-relatie. Bewijs vervolgens 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?
  • Geef informeel de definitie van een lineair begrensde automaat (LBA). Argumenteer dat het aanvaardingsprobleem voor LBA's (A_{LBA}) beslisbaar is. Geef de stappin in een bewijs dat E_{LBA} (de verzameling van LBA's die de lege taal bepalen) niet beslisbaar is.

27 januari (voormiddag)

  • Geef de definitie van een Myhill-Neroderelatie over L. Bewijs dat zo'n MN(L) bestaat alss L regulier is. Bestaat er meer dan één MN(L) voor een gegeven L?
  • Bespreek de 2 noties van reduceerbaarheid (A <=_m B en A <=_T B), hun verband en op welke manier deze kunnen gebruikt worden om aan te tonen dat talen (on)beslisbaar/herkenbaar zijn.

2011

31 januari (voormiddag)

  • Geef de stelling van Rice en bewijs deze. Geef minstens één voorbeeld van een taal dat niet aan de voorwaarden van de stelling voldoet en laat zien dat de stelling dan niet niet-beslisbaarheid impliceert. Bewijs dat alle eigenschappen van Turing machines hiermee uitgedrukt kunnen worden.
  • Geef de conversie regels bij de lambda calculus. Geef de beide stellingen van Chuch-Roser. Geef een voorbeeld hoe je een puur recursieve functie in lambda calculus zou definiëren (ander voorbeeld dan de FAC uit de cursus)
  • Oefening: een gegeven taal, is deze regulier of niet? Bewijzen (constructie van DFA, pompend lemma,...)

28 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".
  • 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?
    • Bijvraag: zou je ook de MN(L)-relatie van een PDA kunnen definieren? Waar loopt het precies mis?
  • Een n-NFA is een machine die eruitziet als een NFA, maar waarvoor een nieuwe definitie van aanvaarden geldt, namelijk: een string s wordt aanvaard door een n-NFA, indien je door delta te gebruiken je in n verschillende accepterende eindtoestanden kan terechtkomen.
    • Bewijs of geef een tegenvoorbeeld van de uitspraak: Voor elke n is de taal van strings geaccepteerd door een n-NFA regulier.
    • Bijvraag: wordt elke reguliere taal ook geaccepteerd door een n-NFA, voor een willekeurige n?

24 januari (namiddag)

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


17 januari (voormiddag)

  • Bespreek in 5 minuten het relevante rond Chomsky hiërarchie
  • Orakelmachines :
    • Wat is een orakelmachine?
    • Leg uit "een orakelmachine is sterker dan een turingmachine" (verklaar ook wat sterker betekent).
    • Kan een verzameling orakelmachines elke taal beslissen?
  • Gegeven Tn(a1a2...ak) = ana2na3n...

of in woorden: Tn selecteert uit een string enkel de tekens die op een plaats i staan zodanig dat i modulo n = 0. Je kan Tn uitbreiden naar een verzameling van strings L als volgt: Tn(L) = {Tn(s) | s ε L} Gegeven een reguliere taal L over alfabet Σ = {a,b}. Bewijs dat Tn(L) ook regulier is. Als dat niet lukt: bewijs het voor bepaalde n; of geef bewijs of tegenvoorbeeld dat het niet waar is (eventueel voor bepaalde n). Zorg dat je argumenten formeel onderbouwd zijn!

2010

22 januari (voormiddag)

  • Geef de stelling van Rice en bewijs deze. Geef minstens één voorbeeld van een taal dat niet aan de voorwaarden van de stelling voldoet en laat zien dat de stelling dan niet niet-beslisbaarheid impliceert. Bewijs ook dat elke niet-triviale, taal-invariante eigenschap kan worden omgevormd tot het IsInTM,S probleem.
  • Geef de conversie regels bij de lambda calculus. Geef de beide stellingen van Chuch-Roser. Geef een voorbeeld hoe je een puur recursieve functie in lambda calculus zou definiëren (ander voorbeeld dan de FAC ui de cursus)
  • Gegeven een taal len(L) die de taal bevat opgemaakt uit de lengtes van alle strings uit de taal L. Deze lengte wordt weergegeven in een unaire notatie me het symbool 'a' (string lengte 0 => a, 1 => aa ...).
    • Als L regulier is, is len(L) dan ook regulier
    • Als L contextvrij is, is len(L) dan ook contextvrij (en regulier ?)
    • Als de notatie naar een binaire weergave van lengte van de strings (0 => a , 1=>b , 2=>ba) , gelden bovenstaande dan nog

18 januari (namiddag)

Media:A&B.pdf

18 januari (voormiddag)

  • Geef de jou bekende methodes om de volgende eigenschappen van talen aan te tonen. Geef telkens ook de stelling waarop de methode steunt:
    • Regulier / niet regulier
    • Contextvrij / niet contextvrij
    • Beslisbaar / niet beslisbaar
  • Geef de definitie van een PDA. Leg de constructie uit van een PDA voor een gegeven contextvrije taal. Beargumenteer de correctheid.
  • S is een taal over alfabet {a,b} en L een taal over alfabet {a,b,c}. We kunnen een functie met signatuur gebruiken.

is gedefinieerd als volgt:

is van de vorm: , waarbij elke een string is over alfabet {a,b} en elke , dan is de string die je bekomt door elke die een element is van de taal S te verwijderen uit .
Indien geen c's bevat is gelijk aan indien een element is van S en gelijk aan in het andere geval.

Dan kunnen we uitbreiden tot een taal: . Gegeven: Talen S en L zijn regulier. Vraag: Bewijs dat een reguliere taal is of bewijs het tegendeel.

11 januari (namiddag)

  • 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?
  • Bewijzen dat de orakelmachine O^A_TM voor E_TM beslisbaar is.
  • s is een string uit een alfabet {a,b}. Gezocht : L_0, de taal zonder s als substring. Een taal L_1, waarin s één keer in voorkomt.

11 januari (voormiddag)

  • Geef in 5 minuten zoveel mogelijk relevante informatie over de Chomsky hiërarchie.
  • Wat is een orakelmachine. Bespreek de uitspraak: "de verzameling orakelmachines (over 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?
  • OEF: Gegeven een rij operatoren Tn (n = 2..) met signatuur Σ -> Σ gedefinieerd als volgt:

Tn(a1a2...ak) = ana2na3n... of in woorden: Tn selecteert uit een string enkel de tekens die op een plaats i staan zodanig dat i modulo n = 0. Je kan Tn uitbreiden naar een verzameling van strings L als volgt: Tn(L) = {Tn(s) | s ε L} Gegeven een reguliere taal L over alfabet Σ = {a,b}. Bewijs dat Tn(L) ook regulier is. Als dat niet lukt: bewijs het voor bepaalde n; of geef bewijs of tegenvoorbeeld dat het niet waar is (eventueel voor bepaalde n). Zorg dat je argumenten formeel onderbouwd zijn!

2009

27 augustus (namiddag)

  • 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?
  • 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".
  • Gegeven een reguliere taal L. Bewijs Dat de taal L'={ hak1(s) | s is een element van L} waarbij hak1(s) het laatste karakter van de string weglaat, ook een reguliere taal is.

30 januari (namiddag)

  • 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?
    Mondelinge bijvraag: Hoe zit het met MN(L)-relaties bij PDA's?
  • 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 met behulp van een pompend lemma dat de taal niet regulier en niet context-vrij is.

30 januari (voormiddag)

  • Geef de definitie van een PDA. Geef de algemene constructie van een CFL naar een PDA. Wat kan je zeggen over het determinisme van deze automaat?
  • Geef de stelling van Rice en bewijs deze. Geef minstens één voorbeeld van een taal dat niet aan de voorwaarden van de stelling voldoet en laat zien dat de stelling dan niet niet-beslisbaarheid impliceert. Bewijs ook dat elke niet-triviale, taal-invariante eigenschap kan worden omgevormd tot het probleem.
  • Beschouw een taal L waarbij elke string van even lengte is. Zij de taal . Bewijs dat L regulier is als en slechts as twist(L) regulier is.

26 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 ATM 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 ATM herkenbaar? Co-herkenbaar? Bestaan er talen die noch herkenbaar noch co-herkenbaar zijn? Heb je een voorbeeld?
  • OEFENING: Definieer de taal Langer(L,n) als alle strings uit de taal L die een lengte hebben groter dan n. Is Langer(L,n) regulier als L regulier is?
  • OEFENING: Toon aan dat de outputtaal van een transducer regulier is.

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 (voormiddag)

  • 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?
    • Is ATM beslisbaar?
    • Is ATM herkenbaar? Zoja, geef eens een herkenner.
    • Hoe kan het orakel in eindige tijd beslissen? Wanneer is een encodering dan redelijk?
    • Kan een orakelmachine alle talen beslissen? En herkennen?
  • Geef de definitie van een PDA. Hoe kan je vanuit een gegeven CFG een PDA construeren? Argumentatie over correctheid van het algoritme.
    • Is die PDA deterministisch?
    • Wat is deterministisch precies?
    • Wanneer wordt een string door een PDA aanvaardt? En door een CFG?
    • Leg uit ambiguiteit van de CFG.
    • Leidt ambiguiteit altijd tot een niet-deterministische PDA? En vice-versa?
  • 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?
  • OEFENING: 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?
  • OEFENING: 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?
  • OEFENING: 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.
  • OEFENING: 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
  • OEFENING: 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?
  • OEFENING: 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.