Inhalt

Behandelt werden die klassischen Themen der theoretischen Informatik aus dem Bereich der formalen Sprachen und Automaten.

Sprachen

• Alphabet, Wort, Sprache
• Mächtigkeit der Menge aller Wörter und der Menge aller Sprachen

Reguläre Sprachen

• Regulärer Ausdruck, reguläre Sprache
• Reguläre Ausdrücke in Programmier­sprachen
• Syntax­diagramm
• Erkennung von regulären Sprachen mit nicht­deterministischen endlichen Automaten
• Nichtdeterministischer endlicher Automat mit Epsilon-Übergängen
• Äquivalenz von nicht­deterministischen endlichen Automaten ohne und mit Epsilon-Übergängen
• Konstruktion eines nicht­deterministischen endlichen Automaten aus einem regulären Ausdruck
• Konstruktion eines regulären Ausdrucks aus einem nicht­deterministischen endlichen Automaten
• Konstruktion eines deterministischen endlichen Automaten aus einem nichtdet. endlichen Automaten
• Komplexität deterministischer endlicher Automaten
• Abgeschlossenheits­eigenschaften regulärer Sprachen
• Pumping-Lemma für reguläre Sprachen

Grammatik

• Grammatik
• Chomsky-Hierarchie der Grammatik­typen
• Konstruktion einer rechts­linearen Grammatik aus einem nicht­deterministischen endlichen Automaten

Kontextfreie Sprachen

• Kontextfreie Grammatik
• Normalisierung von kontext­freien Grammatiken
• Chomsky-Normalform
• Greibach-Normalform
• Pumping-Lemma für kontextfreie Sprachen
• Stackautomat
• Konstruktion eines nicht­deterministischen Stack­automaten aus einer kontext­freien Grammatik
• CYK-Algorithmus

Recursive-Descent-Methode

• Recursive-Descent-Parser und -Übersetzer

Turing­maschinen

• Turing­maschine
• Chomsky-Hierarchie der Automaten­typen
• Reduktion von Wörtern
• String-Turing­maschine
• Chomsky-Hierarchie der String-Turing­maschinen  

Lindenmayer-Systeme

• D0L-Systeme
• Raumfüllende Kurven
• Fraktale

Aufgaben und Literatur

• Aufgaben
• Literatur