Tentamenstof Fundamenele Informatica 3, voorjaar 2012
=====================================================
Inclusief verwijslijst tussen vierde editie (= officiele editie)
en derde editie van boek:
 John C. Martin - Introduction to Languages and the Theory of Computation
(opgesteld, 21 mei 2012)
(aangevuld met opgaven, 7 juni 2012)


In vierde editie boek:                  In derde editie boek:
======================                  =====================

Hst. 5 TOT (niet MET) Vb. 5.34          Hst. 7 TOT (niet MET) Vb. 7.11
behalve preciese (inductie-)details     behalve preciese inductiedetails
van bewijzen van                        van bewijzen van
- St. 5.18                              - St. 7.2
- St. 5.23                              - (staat niet in derde editie)
- St. 5.29                              - St. 7.4

Let op
- dat linksrecursie elimineren en factoriseren in vierde editie `slechts'
  wordt behandeld in opgaven 5.39-5.43, terwijl het in derde editie
  `gewoon' in het theoriedeel van Hst 7 staat. Het onderwerp hoort ook
  dit jaar echter gewoon tot de tentamenstof.


Paragrafen 6.2 en 6.3                   Paragrafen 8.2 en 8.3
behalve preciese inductiedetails        behalve preciese inductiedetails
van bewijs van                          van bewijs van
- St. 6.13                               - St. 8.4

Als hier boven vermeld staat dat de preciese (inductie-)details van een bewijs
niet tot de tentamenstof behoren, moet je nog wel het idee achter het bewijs
kennen.


Hst. 7 helemaal                         Hst. 9 helemaal

Let op
- dat in vierde editie een andere (standaard) notatie wordt gebruikt voor
  een configuratie van een Turing machine dan in derde editie.
  Beide notaties zijn toegestaan op het tentamen
- dat het bewijs van St. 7.26 in vierde editie anders is
  dan het bewijs van de ermee corresponderende St. 9.1 in derde editie
- dat het bewijs van St. 7.31 in vierde editie anders is en minder details
  kent dan het bewijs van de ermee corresponderende St. 9.2 in derde editie


Hst. 8 helemaal                         Hst. 10 helemaal

Let op
- dat in vierde editie wordt gesproken over `deciding a langauge'
  terwijl hetzelfde begrip in derde editie (ook) `recognizing a language'
  heet.


Hst. 9 behalve                          Hst. 11 behalve
- technische details van bewijs van     - technische details van bewijs van
  St. 9.16 (constructie uit het bewijs    St. 11.11 (constructie uit het bewijs
  moet je wel kennen)                     moet je wel kennen)
- bewijs van St. 9.22                   - Lemma 11.2, St. 11.14 en bewijs
                                          van Lemma 11.3

Let op
- dat het beslissingsprobleem WritesNonBlank uit St. 9.10 in vierde editie,
  in de derde editie `slechts' in opgave 11.15 wordt behandeld



Bij beide edities van het boek behoren uiteraard ook de opgaven over
de vermelde stof tot de tentamenstof.

Bij de vierde editie betreft het de volgende opgaven:

5.1-5.43
6.8-6.9, 6.12-6.15, 6.20-6.24
7 allemaal
8 allemaal
9 allemaal