**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