Formele Talen 2010-2011

Hoorcollege

Werkcollege

Boek

Extra stof

Tentamen

Inleveropgaven

Slides van het 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, 3.3: Reguliere expressies, equivalentie van reguliere expressies en eindige automaten, string matching, lexicale analyse, rechts-lineaire grammatica's
3. 2.4, 4.3, 4.2, 5.1, 5.2: Minimale dfa's, pompstelling voor reguliere talen, elementaire eigenschappen van reguliere talen, contextvrije talen, afleidingsbomen, ambiguiteit
4. 6.1, 6.2, 6.3, <8 uit Grune en Jacobs>: Vereenvoudigen van contextvrije grammatica's, Chomsky normaalvorm, CYK parseer-algoritme, LL parseren
5. <9.4, 9.5, 9.6 uit Grune en Jacobs>: LR(0) parseren, SLR(1) parseren, LR(1) parseren, LALR(1) parseren
6. 7.1, 7.3, <3.4 uit Lewis en Papadimitriou>, 7.2: nondeterministische pushdown automaten, deterministische pushdown automaten, equivalentie van contextvrije grammatica's en nondeterministische pushdown automaten
7. 8.1, 8.2, 9.1, 9.3, 10.2, 10.3: Pompstelling voor contextvrije talen, elementaire eigenschappen van contextvrije talen, deterministische Turing machines, Church-Turing these, Turing machines met meerdere tapes, nondeterministische Turing machines
8. 10.4, 11.1, 11.2, 11.3, 10.5, 11.1, 11.4: Universele Turing machine, recursief opsombare talen, onbeperkte grammatica's, context-sensitieve grammatica's, lineaire begrensde automaten, recursieve talen, Chomsky hierarchie
9. 12.1, 12.2, <12.4 uit Sudkamp>, 12.3: Onbeslisbaarheid, halting probleem, stelling van Rice, Post correspondence probleem, onbeslisbare problemen voor contextvrije talen
10. Hoofdstuk 14, <7.2 uit Lewis en Papadimitriou>: Complexiteitsklassen P en NP, polynomiale-tijd reductie, NP-compleetheid, bounded tiling probleem, satisfiability probleem
11. <17.3, 17.4 uit Sudkamp>: PSpace, stelling van Savitch, PSpace-compleetheid, EXP en NEXP
12. <10.1, 10.2, 10.3 uit Arora en Barak>: Qubits, verstrengeling, quantum-operaties, pariteit-spel, quantum-circuits
13. <10.5, 10.7 uit Arora en Barak>, <4.1 uit Bruss et al.>: Superdense coding, algoritme van Simon, complexiteitsklassen BQP en BPP, quantum-cryptografie, BB84 protocol

Opgaven werkcollege (4e editie)

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
   2.3: 2,3,6,12
2. 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
   3.3: 1,3,6,12
   4.1: 17,20,26 (``regular'' moet ``right-linear'' zijn, 2x)
3. 2.4: 1,4,6
   4.3: 1,3,4(e,f)
   5.1: 2,7(b,e),8(b,h),21,22
   5.2: 3,5,9,14
4. JFLAP practicum opdracht
5. 6.1: 6,7,9,15,16
   6.2: 3,4
   6.3: 1,2,3
   opgaven 1 t/m 4 van de extra exercise sheet
6. 7.1: 3(a),4(c,g),5,11
   7.2: 5,6,15
   7.3: 3,5,8
7. 8.1: 2,3,5,8(c)
   8.2: 1,11,22,23
   7.3: 16,18
8. 1e collectie inleveropgaven
   9.1: 4,5,7(d,e),8
9. 11.1: 3,6,7,8,10
   11.2: 6,7
   11.3: 1(b,d),3
   10.5: 4(c,d)
10. 12.1: 3,7,9
    12.3: 1,3
    14.2: 5
    14.3: 2,3
    opgave 7.2.2(c) uit Lewis en Papadimitriou
11. 2e collectie inleveropgaven
12. Voorbeeldtentamen

Opgaven werkcollege (3e editie)

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.3: 2,3,6,12
2. 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: 1,3,5,11
   4.1: 17,20,26 (``regular'' moet ``right-linear'' zijn, 2x)
3. 2.4: 1,4,6
   4.3: 1,3,4(e,f)
   5.1: 2,7(b,e),8(b,h),20,21
   5.2: 3,5,9,14
4. JFLAP practicum opdracht
5. 6.1: 6,7,9 (``Exercise 7'' moet ``Exercise 6'' zijn),14,15
   6.2: 3,4
   6.3: 1,2,3
   opgaven 1 t/m 4 van de extra exercise sheet
6. 7.1: 3(a),4(c,g),5,11
   7.2: 5,6,15
   7.3: 3,5,8
   
7. 8.1: 2,3,5,8(c)
   8.2: 1,11,22,23
   7.3: 16,18
8. 1e collectie inleveropgaven
   9.1: 4,5,7(d,e),8
9. 11.1: 3,6,7,8,10
   11.2: 6,7
   11.3: 1(b,d),3
   10.5: 4(c,d)
10. 12.1: 3,7,9
    12.3: 1,3
    14.2: 6
    14.3: 2,3
    opgave 7.2.2(c) uit Lewis en Papadimitriou
11. 2e collectie inleveropgaven
12. Voorbeeldtentamen

Oude tentamens

Nuttige links