Dit vak wordt niet meer gegeven. Vervanging is het college Fundamentele Informatica 2.

Formele Talen en Automaten 1

najaar 2003

Docent: Het vak Formele Talen en Automaten 1 wordt in het najaarssemester van 2003 voor de deeltijdopleiding verzorgd door Joost Engelfriet.

Rooster: Er is college op maandagavond van 18.45 uur tot 21.45 uur, in zaal 1 van het Gorlaeus Laboratorium. Voor details zie het precieze rooster.

Laatste tentamen! vrijdag 16 april 2004, 19-22 uur, ook in zaal 1 van het Gorlaeus Laboratorium.

Voorkennis: het college Inleiding Fundamentele Informatica.

In het voorjaarssemester 2003 werd het vak verzorgd door Jetty Kleijn (webpagina's: college en werkcollege).

FTA1 in 2003-2004

In het studiejaar 2003-2004 wordt het college Formele Talen en Automaten 1 voor het laatst ('s avonds in het najaarssemester) gegeven. Overdag geldt al het nieuwe (bachelor)programma met de vakken Fundamentele Informatica 2 (Formele Talen) en Fundamentele Informatica 3 (Berekenbaarheid). Voor nadere inlichtingen kan men zich wenden tot de docenten: Joost Engelfriet en Jetty Kleijn.

Materiaal

collegedictaat: Formele Talen en Automaten 1, G. Rozenberg, H.J. Hoogeboom, en J. Engelfriet (nr. 505066, voorjaar 2000); Opgavenbundel FTA1 (nr. 505074, voorjaar 2000).
Inhoudsopgave [ps, 53kb]
Index op stellingnummer [ps, 104kb]
Errata [ps, 68kb]

aanbevolen literatuur: T.A. Sudkamp, Languages and Machines, Addison-Wesley, 1997.
J. Hopcroft, J. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1980.
Deze boeken zijn niet noodzakelijk om het college te kunnen volgen.

Uitwerkingen

Geselecteerde uitwerkingen uit de opgavenbundel:

Programma van het college

iw = i uur werkcollege, ih = i uur hoorcollege; het werkcollege wordt altijd vóór het hoorcollege gegeven.

De nummers voor het werkcollege verwijzen naar de opgaven in de opgavenbundel,
de nummers voor het hoorcollege verwijzen naar de hoofdstukken in het dictaat.

Dit programma is uiteraard maar een benadering.

Programma FTA1
nr datum werkcollege hoorcollege
1 1/9 0w 3h: 1, 2, 3.1-3.6
2 15/9 1w: 3.4-3.7 2h: 3.7, 3.8
3 22/9 2w: 3.8, 3.9, 3.10, 3.11a, 3.12, 3.14, 3.15,
3.18, 3.19, 3.22, 3.23
1h: 3.9
4 6/10 1w: 3.38, 3.39, 3.40, 3.24, 3.36 2h: 3.11
5 13/10 1w: 3.28-3.32 2h: 4.1-4.4, 3.12, 4.7
6 27/10 1w: 4.1bce, 3.41, 3.42, 4.9, 4.4, 4.5 2h: 4.5, 4.6
7 3/11 1w: 4.6, 4.7, 4.11, 4.12, 4.14 2h: 4.9, 4.10
8 10/11 2w: 4.15, 4.16, 4.19, 4.20, 4.23, 4.26,
4.24, 4.25, 4.18, 4.21
1h: 5.1, 5.3
9 24/11 1w: 5.1cd, 5.2ac, 5.3, 5.9, 5.10ad 2h: 5.2, 5.4
10 1/12 1w: 5.4, 5.5, 5.7, 5.8, 5.11-5.14 2h: 5.5, 6.3, 6.4
11 15/13 2w: 5.15, 5.16, 6.1a, en wat nog over is 1h: 6.1, 6.2

Collegetijden: 18.45-19.45, 20.00-20.45, 21.00-21.45 uur

Tentamen

Het tentamen is een open-boek-tentamen. Boeken, dictaat, uitwerkingen en aantekeningen mogen dus meegebracht worden.

Er zal niet getentamineerd worden over de `algebraische representatie' van reguliere talen, en ook niet over `zelf-inbeddende' context-vrije grammatica's.

tentamen: woensdag 14 januari 2004, 19-22 uur
hertentamen: vrijdag 16 april 2004, 19-22 uur

Oefenstof

Hieronder oude stijl tentamens en uitwerkingen, maar nog steeds heel erg nuttig om te oefenen! Deze files kunnen natuurlijk ook geprint worden.


17.9'04   -   /home/hoogeboo/fta1.html