**2022**

1. toon aan dat de doorsnede van een reguliere en een contextvrije taal opnieuw contextvrij is
2. Formuleer het halting probleem, bewijs de onbeslisbaarheid ervan en geef een praktisch consequent ervan


1. Geef pompstelling van reguliere talen en toon het aan met een CFG 
2. Formuleer het halting probleem, bewijs de onbeslisbaarheid ervan en geef een praktisch consequent ervan


Doorsnede van reguliere en pumping lemma CFG met voorbeeld op een CFG waren myn vragen


Pumping lemma uitleggen en met voorbeeld CFG illustreren
+ halting probleem bewijzen en praktisch gevolg


Bewijs dat de doorsnede van een contextvrije taal en een reguliere taal opnieuw contextvrij is.
Bespreek reductie in de context van berekenbaarheid en geef een voorbeeld van een onberekenbaar probleem.


1) Bespreek reductie in context van de berekenbaarheid
2) Pumping van CFL


1) Pcp uitlegge en aantone da doorsnede tusse cfls onbeslisbaar is
2) Bewijs dat reguliere talen kunne beschreve worde door RegEx

Pump cfl + aantonen dmv tree, halting problem + belang

**2023**
1: Toon aan dat voor elke NFA er een equivalente DFA bestaat
2: Toon aan dat de verzameling van Turing Machines aftelbaar oneindig is


bewijs dat we nfa kunnen omzetten naar dfa,
formuleer en bewijs halting + geef gevolg,
bijvragen waren:
kan je dan ook een npda naar een dpda veranderen,
gwn uitleggen wat er staat,
hoe noem je het type bewijs van halting: contradictie,


bewijs over reguliere talen en reguliere expressies(3.2) en halting uitleggen + bewijs + gevolg(reduceren)


Pumpinglemma RL + vb,
every word Halting problem,


Arbitrary sized problem. Give techniques seen in the course to solve this on  finite hardware. (30%)
Proof why  emptiness of unrestricted grammar is undecidable. Proof why  infiniteness of unrestricted grammar is undecidable. Significance of undecidability in computational theory (70%)


**2024**

CFL:
Wa is da?
Geef vb.
Hoe weet algo da het CFG is en ni RL?
Gebt zo unit prod, null prod, useless prod. Geef mij algoritmes voor elk van deze uit te voeren en zeg mij hoe deze bewijst worden.
Hoe kan je deze parsen ofzoiets
Geef RealLife expls van RegLang, CFL, CSL, REL


Décidabilité on CFG’s, emptiness/infiniteness. Dépendent graph, ..
Non-determinism (definiëren)


LBA <=> CSL
een CPU is een DFA?


Eerste vraag: wat is de relatie tussen context sensitive languages en LBA, leg uit en definieer hoe een LBA werkt. Geef ook het bewijs waarom alle context sensitive languages geaccepteerd worden door een LBA. Geef een voorbeeld van een contect sensitive language met bijhorende lba.
2e vraag:
Argumenteer waarom Excel Turing compleet is en ze dezelfde computational power hebben


Vraag: dpda’s en npda’s, alles uitleggen 
Vraag: iets met simulation van turing machine is transitive, proof + uitleggen


Vraag reeks 1: vraag 1)
a) contruct een DFA given NFA.
b) proof that for any given string as nfa accept it that DFA accept it
c)contruct NFA given a DFA
Vraag 2
Give the shompsky hiërarchie and examples of real life


1) CFG simplification
Wat is een grammar
Wat is een CF grammar
Useless/null/unit rules:
Uitleggen+algo+voorbeeld
2) wat zijn de stappen van een compiler en hoe is het gerelateerd met de geziene leerstof


moest hoog niveau uitleggen en dan het algoritme ervoor geven


Question 1
1. Define  ‘unrestricted grammar’ and ‘Recursively enumerate languages’,
2. Prove unrestricted grammar => Recursive Enumerable language,
3. Explain it from the Chomsky hierarchy,
4. …,

Question 2
Define non-determinism and the term usefulness. Compare non-determinism and determinism and give the advantages from non-determinism. Give an example of it in the real world.


1a) leg het proces uit om van een right linear grammar naar een FA te gaan
1b) bewijs voor Right lineair grammar => Reguliere taal
1c) geef een voorbeeld van RLG naar FA of regex (70%)

2) hoe kunnen computers met een eindig aantal geheugen, theoretisch    inf concepten voorstellen? Virtual memory and Dynamic memory allocation, welke concepten hebben we gezien die hier op lijken/zelfde zijn. (30%)


Ik had 1) (op 7 punten) 
1.leg uit wat een turing machine is, leg operaties uit enzo
Wat is het haltings probleem, wat is de link met computational theorie,
Bewijs het halting probleem,
2) (op 3 punten) leg alle stappen uit van het compiler van source code naar executable. Bij elke stap geef gelijkenissen (algoritmes en datastructuren) met de geziene leerstof

Question 1:
Closure of regular languages under complement
Closure of regular languages under concatenation
Closure of regular languages under union
Closure of regular languages under Kleene closure (L*)
Closure of regular languages under intersection
Question 2:
Give a real-life example of regular language, context-free language, context-sensitive and recursively enumarable language. Discuss some conclusions we made about these languages during the course.


undecidable problem
Arbitrary sized problem. Give techniques to solve this on a finite hardware.
Proof why emptiness of unrestricted grammar is undecidable. 
Proof why infiniteness of unrestricted grammar is undecidable.
Significance of undecidability in computational theory


Vraag 1) Turing machines
A) allemaal varianten, leg ze uit
B) equivalentie tussen basic TM en die varianten
C) kan je van basic TM naar variant en terug ( zo iets ) en dan ook zo me powerfull enzo ma da sta er nie op da moe ge gwn zeggen
En dan vraag 2) die DPA = GPU?


Vraag 1: Lba en context sensitive
definitie lba en context sensitive language,
proof: Lba accepts context sensitive,
Lba significancy in chomsky hierarchy,
Voorbeeld en teken,

Vragen 2: turing machine simulation transitive
sketch proof and examples and where used in the course,
Vraag 2 is basically hoe het simuleren van de variaties van TM die we hebben gezien transitief is.


Vraag 1:
Geef carters diagonal om te argumenteren iets me oneindige sets van getallen ofzo
Geef een formeel bewijs waar in het gebruikt word
Iets me de importance in computational boel dervan
Vraag2
Leg uit non deterministisch en het gebruik ervan, geef voordelen, vergelijk me deterministisch, geef modellen die het hebben, geef voorbeeld ervan in real life

