[Tuyaux] Examenvragen 2e zit Machines en Berekenbaarheid

Forum van 2de Bachelor Informatica.

Moderator: Praesidium

User avatar
Sebastiaan
Posts: 1184

[Tuyaux] Examenvragen 2e zit Machines en Berekenbaarheid

Post#1 » 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
WINAK Schacht 2007-2008
WINAK Commiliton 2008-2009
ASK-Stuwer Snelkrant 2009-2010
ASK-Stuwer Vice-Praeses 2010-2011
ASK-Stuwer Praesidium 2011-2012
ASK-Stuwer IT 2012-2013

Return to “2de Bachelor”

Who is online

Users browsing this forum: No registered users and 5 guests

cron