Die Vorlesung richtet sich nach dem Buch "Theoretische Informatik kurzgefasst" von Uwe Schoening, 4. Aufl, korrigierter Nachdruck. 


Folgende Abschnitte aus Schoenings Buch wurden *nicht* in der
Vorlesung behandelt. 

*) Endlichkeitsproblem fuer regulaere Sprachen, S.50
*) Greibach Normalform fuer kontextfreie Sprachen, S.54ff
*) Regularitaet kontextfreier Sprachen ueber einelementigem Alphabet, S.62
*) Deterministisch kontextfreie Sprachen, S.76ff. Es wurde nur erwaehnt, 
   dass deterministische PDA weniger maechtig sind als PDA. 
   Allerdings wurden deterministische PDA ausfuehrlich in Uebungsaufgaben 
   behandelt. 
*) Endlichkeitsproblem fuer kontextfreie Sprachen. 
*) Beweis des Satzes von Immerman-Szelepcsenyi (Komplementabschluss der Typ-1 Sprachen)
*) Tabellarischer Ueberblick der Resultate zu formalen Sprachen, soweit nicht bereits abgedeckt, S.88ff. 
*) Die Konstrukte WHILE und Wertzuweisung direkt auf Turingmaschinen, S.98ff. 
   Stattdessen wurde direkt gezeigt, wie WHILE Programme auf 
    Turingmaschinen simuliert werden koennen. 
*) NP-haerte des Wortproblems fuer Typ 1 Sprachen und der Nichtaequivalenz regulaerer Ausdruecke. 
*) Schlussbetrachtungen ueber Heuristiken fuer NP-vollstaendige Probleme. 
*) Der Goedelsche Unvollstaendigkeitssatz wird in der Vorlesung nur relativ kursorisch behandelt. 
   Details der Schoeningschen Durchfuehrung sindf nicht pruefungsrelevant. Die zentrale Aussage allerdings schon. 


Folgende Definitionen wurden leicht abgeaendert: 

*) Akzeptierte Sprache eines NEA: In Vorlesung ueber Existenz akzeptierender Laeufe; bei Schoening durch formale 
   Erweiterung der Uebergangsrelation auf Zustandsmengen. 


Darueberhinaus gab es in der Vorlesung andere und mehr Beispiele und
manche Beweise wurden etwas anders gefuehrt als in Schoenings Buch.

Alle Konzepte, Saetze, Beweise, die nicht explizit hier ausgeschlossen
werden, wurden in der Vorlesung behandelt und sind somit
Pruefungsstoff.