Inhalt
Teil I: Formale Sprachen
1 Grundlagen
2 Endliche Automaten
3 Reguläre Sprachen und reguläre Ausdrücke
4 Reguläre Grammatiken
5 Kontextfreie Sprachen
6 Kellerautomaten
7 Eigenschaften kontextfreier Sprachen
8 Spezielle Entscheidungsalgorithmen für kontextfreie Sprachen
9 Die Chomsky-Hierarchie
Teil II: Berechenbarkeit
10 Turing-Maschinen
11 Turing-Aufzählbarkeit, -Akzeptierbarkeit, -Berechenbarkeit,
-Entscheidbarkeit
12 Primitiv rekursive und partiell rekursive Funktionen
13 Turing Maschinen und partiell rekursive Funktionen
14 LOOP- und WHILE-Programme
15 Aufzählbarkeit
16 Unentscheidbarkeit
Literatur