Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456
Formele Talen 2005-2006
[go: Go Back, main page]

Formele Talen 2006-2007

Hoorcollege

week 40-42: vrijdag 11:00-12.45 in zaal 04A05 (hgb).
week 44-50: donderdag 11:00-12:45 in zaal S203.
docent: Wan Fokkink.

Werkcollege

week 40-42: vrijdag 13:30-15:15 in zaal F647.
week 44-50: vrijdag 13:30-15:15 in zaal S205.
docent: IJsbrand Oudshoorn.

Boek

Peter Linz, An Introduction to Formal Languages and Automata, Jones and Bartlett, 2001 (3e druk)

Inleveropgaven

Na het derde en zesde hoorcollege worden inleveropgaven op deze webpage geplaatst. Beide inleveropgaven kunnen 0.25 bonuspunt opleveren voor het tentamen.

Slides hoorcollege

Download hier de slides.

Stof hoorcollege

  1. 1.2, 2.1, 2.2: Talen als verzamelingen, grammatica's, deterministische eindige automaten, nondeterministische eindige automaten

  2. 2.3, 3.1, 3.2, 4.1, 4.2: Equivalentie van deterministische en nondeterministische eindige automaten, reguliere expressies, elementaire eigenschappen van reguliere talen

  3. 3.3, 2.4, 4.3: Rechts-lineaire grammatica's, minimale dfa's, pompstelling voor reguliere talen

  4. 5.1, 5.2, 6.1, 6.2, 6.3: Contextvrije talen, afleidingsbomen, ambiguiteit, vereenvoudigen van contextvrije grammatica's, Chomsky normaalvorm, CYK algoritme

  5. 7.1, 6.2, 7.2: Nondeterministische pushdown automaten, Greibach normaalvorm, van contextvrije grammatica's naar nondeterministische pushdown automaten

  6. 7.2, 8.1, 8.2, 7.3: Van nondeterministische pushdown automaten naar contextvrije grammatica's, pompstelling voor contextvrije talen, elementaire eigenschappen van contextvrije talen, deterministische pushdown automaten

  7. 9.1, 9.3, 11.1, 11.2: Turing machines, Church-Turing these, recursief opsombare talen, onbeperkte grammatica's

  8. 11.1, 11.3, 10.5, 11.4: Recursieve talen, context-sensitieve grammatica's, lineaire begrensde automaten, Chomsky hierarchie

  9. 12.1, 12.3: Onbeslisbaarheid, halting probleem, post correspondence probleem

  10. 14.1, 14.2, 14.3, 14.4: Complexiteitsklassen P en NP, polynomiale-tijd reductie, NP-compleetheid, bounded tiling probleem, satisfiability probleem

Opgaven werkcollege

  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
    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
    6.2: 10,13
    7.2: 5,6

  6. 7.2: 15,16
    8.1: 2,3,5,8(c),10
    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
    2e collectie inleveropgaven

  10. 14.2: 3,4,6
    14.3: 2,3
    14.4: 1

Oude tentamens

  • tentamen 2003

  • tentamen 2004

  • tentamen 2005

    • Nuttige link

  • Wikipedia encyclopedia: Formal languages

  • FSA Utilities Toolbox