Automata and formal Languages

Modulnummer
CS2315
Modulverantwortliche
Albert Schneider
Dozenten
  • Michael Jäger
  • Hans-Rudolf Metz
  • Albert Schneider
  • Kurzbeschreibung
    Characterizations and properties of regular and context-free languages and of Turing machines.
    Qualifikations- und Lernziele

    Students are familiar with the principal capabilities and limitations of regular and context-free languages, of computers and of algorithms. Students can use different methods to describe languages. As well, they know about the relationship with syntax analysis. They are able to communicate on theoretical aspects of their „information technology everyday work”.

    Lerninhalte
    • Regular languages: deterministic and nondeterministic finite automata, regular expressions, pumping lemma for regular languages
    • Context-free languages: context-free grammars, pushdown automata, pumping lemma for context-free languages
    • Introduction to syntax analysis: parse trees, scanner, parser
    • Turing machines, decidability, halting problem
    Moduldauer (Semester)
    1
    Unterrichtssprache
    Deutsch
    Gesamtaufwand
    6 CrP; 180 Stunden, davon etwa 60 Stunden Präsenzzeit.
    Semesterwochenstunden
    4
    Lernformen

    Lecture 3 SWS, Exercises 1 SWS

    Geprüfte Leistung

    Examination: Written exam

    Bewertungsstandard
    according to examination regulations (§ 9)
    Häufigkeit des Angebots
    Yearly
    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