Formele Talen 2006-2007

Hoorcollege

Werkcollege

Boek

Extra stof

Tentamen

Inleveropgaven

1. 1e collectie inleveropgaven (Deadline: 16 november, 13:00 uur)
2. 2e collectie inleveropgaven (Extended deadline: 14 december, 15:00 uur)

Slides hoorcollege

Stof hoorcollege

1. 1.1 (vanaf blz 10, "Proof Techniques"), 1.2, 2.1, 2.2, 2.3: Talen als verzamelingen, grammatica's, deterministische eindige automaten, nondeterministische eindige automaten, equivalentie van deterministische en nondeterministische eindige automaten
2. 3.1, 3.2, 4.1, 4.2, 3.3: Reguliere expressies, elementaire eigenschappen van reguliere talen, rechts-lineaire grammatica's
3. 2.4, 4.3, 5.1, 5.2: Minimale dfa's, pompstelling voor reguliere talen, contextvrije talen, afleidingsbomen, ambiguiteit
4. 6.1, 6.2, 6.3, 7.1, 7.3: Vereenvoudigen van contextvrije grammatica's, Chomsky normaalvorm, CYK algoritme, nondeterministische pushdown automaten, deterministische pushdown automaten
5. <3.4 uit Lewis en Papadimitriou>, 7.2, 8.1: Equivalentie van contextvrije grammatica's en nondeterministische pushdown automaten, pompstelling voor contextvrije talen
6. 8.2, 9.1, 9.3, 10.2, 10.3, 11.1: Elementaire eigenschappen van contextvrije talen, deterministische Turing machines, meerdere tapes, nondeterministische Turing machines, Church-Turing these, recursief opsombare talen
7. 11.2, 11.3, 10.5, 11.1, 11.4: Onbeperkte grammatica's, context-sensitieve grammatica's, lineaire begrensde automaten, recursieve talen, Chomsky hierarchie
8. 12.1, 12.2, <12.4 uit Sudkamp>, 12.3: Onbeslisbaarheid, halting probleem, stelling van Rice, post correspondence probleem, onbeslisbare problemen voor contextvrije talen
9. Hoofdstuk 14, <7.2 uit Lewis en Papadimitriou>: Complexiteitsklassen P en NP, polynomiale-tijd reductie, NP-compleetheid, bounded tiling probleem, satisfiability probleem

Opgaven werkcollege (4e druk)

1. 1.2: 2,4,8,10,11(a,b,c),13,14(a,b,e,f,h)
   2.1: 1,2(d),3,7(b),9(b,f),11
   2.2: 12
   UITWERKINGEN
2. 2.3: 2,3,6,12
   3.1: 5,7,13,16(a,b)
   3.2: 1,2,4(b,d),9,10(a,c),13(a)
   4.2: 5,12
   UITWERKINGEN
3. 3.3: 1,3,6,12
   4.1: 17,20,26 (in het antwoord wordt verondersteld dat beide grammatica's rechts-lineair zijn, en bij het antwoord op 26c is S->lambda vergeten)
   2.4: 1,4,6
   4.3: 1,3,4(e,f)
   UITWERKINGEN
4. 5.1: 2,7(b,e),8(b,h),21,22
   5.2: 3,5,9,14
   6.1: 6,7,9,15,16
   6.2: 3,4
   UITWERKINGEN
5. 6.3: 1,2,3
   7.1: 3(a),4(c,g),5,11
   7.2: 5,6,15
6. 8.1: 2,3,5,8(c)
   1e collectie inleveropgaven
7. 8.2: 1,11,22,23
   7.3: 3,5,8,16,18
   9.1: 4,5,7(d,e),8
8. 11.1: 3,6,7,8,10
   11.2: 6,7
   11.3: 1(b,d),3
   10.5: 4(c,d)
9. 12.1: 3,7,9
   12.3: 1,3
   14.2: 5
   14.3: 2,3
   opgaven 7.2.2(c) uit Lewis en Papadimitriou
10. 2e collectie inleveropgaven

Opgaven werkcollege (3e druk)

1. 1.2: 2,4,7,9,10(a,b,c),12,13(a,b,e,f,h)
   2.1: 1,2(d),3,7(b),9(b,f),11
   2.2: 11
2. 2.3: 2,3,6,12
   3.1: 4,6,12,14(a,b)
   3.2: 1,2,4(b,d),9,10(a,c),12(a)
   4.2: 5,12
3. 3.3: 1,3,5,11
   4.1: 17,20,26 (in het antwoord wordt verondersteld dat beide grammatica's rechts-lineair zijn, en bij het antwoord op 26c is S->lambda vergeten)
   2.4: 1,4,6
   4.3: 1,3,4(e,f)
4. 5.1: 2,7(b,e),8(b,h),20,21
   5.2: 3,5,9,14
   6.1: 6,7,9 (``Exercise 7'' moet ``Exercise 6'' zijn),14,15
   6.2: 3,4
5. 6.3: 1,2,3
   7.1: 3(a),4(c,g),5,11
   7.2: 5,6,15
6. 8.1: 2,3,5,8(c)
   1e collectie inleveropgaven
7. 8.2: 1,11,22,23
   7.3: 3,5,8,16,18
   9.1: 4,5,7(d,e),8
8. 11.1: 3,6,7,8,10
   11.2: 6,7
   11.3: 1(b,d),3
   10.5: 4(c,d)
9. 12.1: 3,7,9
   12.3: 1,3
   14.2: 6
   14.3: 2,3
   opgaven 7.2.2(c) uit Lewis en Papadimitriou
10. 2e collectie inleveropgaven

Oude tentamens

Nuttige link