Modulbeschreibung

Automaten und Sprachen

ECTS-Punkte:
4
Lernziele:
  • 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.

Kurse in diesem Modul

Automaten und Sprachen:
  1. 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)
  2. Kontextfreie Sprachen
    (Kontextfreie Grammatiken, deterministische und nicht-deterministische Keller-Automaten, Äquivalenz von regulären Sprachen und Keller-Automaten, Pumping-Lemma für kontextfreie Sprachen)
  3. Berechnungstheorie
    (Turing-Maschinen, Halteproblem, Satz von Rice)
  4. Komplexitätstheorie
    (Die Klassen P und NP, NP-vollständige Probleme)
Vorlesung mit 3 Lektionen pro Woche
Uebung mit 1 Lektionen pro Woche
Disclaimer

Diese Beschreibung ist rechtlich nicht verbindlich! Weitere Informationen finden Sie in der detaillierten Modulbeschreibung.