Inhalt

1. Formale Sprachen
   Alphabet, Sprachen, Grammatiken, Chomsky-Typen: regulär, kontextfrei, Typ 0.

2. Endliche Automaten
   Äquivalenz von deterministischen endlichen Automaten (DFA's), nichtdeterministischen endlichen Automaten (NFA's) und regulären Grammatiken.

3. Eigenschaften regulärer Sprachen
   Abschlusseigenschaften, Äquivalenz mit regulären Ausdrücken, minimaler DFA, effizienter Äquivalenztest, Pumping Lemma.

4. Kellerautomaten
   Äquivalenz von Kellerautomaten (PDAs) mit kontextfreien Grammatiken, deterministische Kellerautomaten.

5. Eigenschaften kontextfreier Sprachen
   Chomsky-Normalform, Pumping Lemma, CYK-Algorithmus, Abschlusseigenschaften.

6. Turingmaschinen
   Äquivalenz mit Typ-0 Grammatiken, Church-Turing These.