Übersicht:

Die Vorlesung gibt eine kompakte Einführung in das Gebiet der Automatentheorie und Formalen Sprachen, das sowohl für die theoretische Informatik (Berechenbarkeitstheorie, Komplexitätstheorie, formale Systeme und Semantik) als auch für die praktische Informatik (Programmiersprachen, Syntaxanalyse, Compilerbau usw.) von grundlegender Bedeutung ist.
Formale Sprachen sind Mengen von Wörtern über einem vorgegebenen Alphabet. Wir untersuchen vier grundlegende Klassen, hier gelistet nach aufsteigender Mächtigkeit:

  • Die regulären Sprachen (geeignet zur Beschreibung lexikalischer Phänomene),
  • die kontextfreien Sprachen (für syntaktische Phänomene),
  • die kontextsensitiven Sprachen
  • und schließlich die rekursiv aufzählbaren Sprachen.

Wir folgen dieser Einteilung und arbeiten für jede dieser vier Klassen die wichtigsten Eigenschaften und Darstellungen (etwa durch Grammatiken oder Automaten) heraus. Der Schwerpunkt liegt dabei auf den regulären und auf den kontextfreien Sprachen.

Einordnung:

Die Vorlesung ist zweistündig, begleitet von Übungen. Die Veranstaltung gehört zum Kanon der Grundvorlesungen im Bachelor-Studium Informatik und bildet gemeinsam mit der Veranstaltung Berechenbarkeit und Komplexität ein Modul, das sich über zwei Semester erstreckt.

Teilnahmevoraussetzungen:

Modul Diskrete Strukturen und Logik bzw. gleichwertige mathematische Kenntnisse und Fertigkeiten

Informationen zum Ausdrucken

Aktualisierte Informationen, Folien, Übungsblätter usf. werden über Stud.IP den angemeldeten Teilnehmerinnen und Teilnehmern zur Verfügung gestellt.