Automaten und formale Sprachen

Modulnummer
CS2315
Modulverantwortliche
Albert Schneider
Dozenten
  • 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