Automata and formal Languages

Module Code
CS2315
Module Coordinators
Albert Schneider
Teachers
  • Michael Jäger
  • Hans-Rudolf Metz
  • Albert Schneider
  • Short Description
    Characterizations and properties of regular and context-free languages and of Turing machines.
    Learning Objectives

    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”.

    Contents
    • 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
    Duration in Semester
    1
    Instruction Language
    German
    Total Effort
    6 CrP; an estimated 180 hours, of which approximately 60 are spent in class.
    Weekly School Hours
    4
    Method of Instruction

    Lecture 3 SWS, Exercises 1 SWS

    Requirements for the awarding of Credit Points

    Examination: Written exam

    Evaluation Standard
    according to examination regulations (§ 9)
    Availability
    Yearly
    References
    • M. Sipser: Introduction to the Theory of Computation
    • J. Hopcroft, R. Motwani, J. Ullman: Einführung in Automatentheorie, Formale Sprachen und Berechenbarkeit
    Prerequisite Modules