Automaten und formale Sprachen

Kurzame
Automaten u. formale Spr
Modulnummer
CS2315
Modulverantwortlicher
  • Albert Schneider
Dozent
  • Michael Jäger
  • Hans-Rudolf Metz
  • Albert Schneider
Kurzbeschreibung
Beschreibungen und Eigenschaften von regulären und kontextfreien Sprachen sowie von Turing-Maschinen.
Qualifikations- und Lernziele

Die Studierenden wissen um die theoretischen Grenzen der Berechenbarkeit und kennen die prinzipiellen Möglichkeiten und Grenzen verschiedener formaler Sprachklassen und Automatenmodelle. Sie verstehen einige wichtige einschlägige Algorithmen und können sie in einfachen Beispielfällen erläutern und anwenden. Sie kennen den Bezug zur lexikalischen und syntaktischen Analyse von Programmiersprachen. Sie sind in der Lage über theoretische Aspekte ihrer informationstechnischen Alltagsarbeit zu kommunizieren.

Lerninhalte
  • Reguläre Sprachen: deterministische und nichtdeterministische endliche Automaten, reguläre Ausdrücke, Pumping-Lemma für reguläre Sprachen
  • Kontextfreie Sprachen: kontextfreie Grammatiken, Pushdown-Automaten, Pumping-Lemma für kontextfreie Sprachen
  • Einführung in die Syntaxanalyse: Ableitungsbäume, Scanner, Parser
  • Turing-Maschinen, Entscheidbarkeit, Halteproblem
Moduldauer (Semester)
1
Unterrichtssprache
Deutsch
Gesamtaufwand
6 CrP; 180 Stunden, davon etwa 60 Stunden Präsenzzeit.
Semesterwochenstunden
4
Lernformen

Seminaristischer Unterricht 4 SWS

Geprüfte Leistung

Prüfungsleistung: Klausur

Bewertungsstandard

Bewertung der Prüfungsleistung nach § 9 der Prüfungsordnung (Teil I)

Häufigkeit des Angebots
Einmal im Jahr
Literatur
  • M. Sipser: Introduction to the Theory of Computation
  • J. Hopcroft, R. Motwani, J. Ullman: Einführung in Automatentheorie, Formale Sprachen und Berechenbarkeit
Vorausgesetzte Module