Automaten und Sprachen

Description

Grundlagen zur Verarbeitung formaler Sprachen. Fähigkeit, formale Spezifikationen (z.B. in BNF) zu erstellen und zu verstehen. Beherrschung verschiedener Berechenbarkeitsbegriffe. Grundlagen der Komplexitätstheorie. Reguläre Sprachen (Reguläre Ausdrücke, deterministische und nicht-deterministische endliche Automaten, Äquivalenz von regulären Sprachen und endlichen Automaten, Pumping-Lemma für reguläre Sprachen) Kontextfreie Sprachen (Kontextfreie Grammatiken, deterministische und nicht-deterministische Keller-Automaten, Äquivalenz von regulären Sprachen und Keller-Automaten, Pumping-Lemma für kontextfreie Sprachen) Berechnungstheorie (Turing-Maschinen, Halteproblem, Satz von Rice) Komplexitätstheorie (Die Klassen P und NP, NP-vollständige Probleme)