[Tuyaux] Examenvragen 2e zit Machines en Berekenbaarheid
Posted: Sat Aug 28, 2010 4:52 pm
Hey, dit waren de vragen van M&B.
Theorie:
1. Geef een overzicht van alle sluitingseigenschappen die we gezien hebben bij CFL
2. Bij het converteren van een CFG naar chomsky normal form is de volgorde van bewerkingen belangrijk. Toon dit aan met een voorbeeld
3. Def DPDA (Deterministische !!)
4. Gegeven 2 verschillende parse trees die naar een zelfde string w gaan. Wat weet je dan over de Left-Most derivations? en bewijs dit
Oefeningen:
1. Maak een Turing Machine voor volgende taal = ( a(^m) b(^n) c(^m*n) | m , n > 0)
2. Is (x(^a) y(^b) z(^c) | a < b < c) Context vrij? Toon dit aan.
3. Zet volgende grammar in chomsky normal form.
L -> () | (FP) | (P)
F -> a | d | epsilon
P -> asP | LsP | a | L | epsilon
Theorie:
1. Geef een overzicht van alle sluitingseigenschappen die we gezien hebben bij CFL
2. Bij het converteren van een CFG naar chomsky normal form is de volgorde van bewerkingen belangrijk. Toon dit aan met een voorbeeld
3. Def DPDA (Deterministische !!)
4. Gegeven 2 verschillende parse trees die naar een zelfde string w gaan. Wat weet je dan over de Left-Most derivations? en bewijs dit
Oefeningen:
1. Maak een Turing Machine voor volgende taal = ( a(^m) b(^n) c(^m*n) | m , n > 0)
2. Is (x(^a) y(^b) z(^c) | a < b < c) Context vrij? Toon dit aan.
3. Zet volgende grammar in chomsky normal form.
L -> () | (FP) | (P)
F -> a | d | epsilon
P -> asP | LsP | a | L | epsilon