Automata and formal Languages

Short Name
Automaten u. formale Spr
Module Code
Module Coordinator
  • Prof. Dr. Albert Schneider
  • Prof. Dr. Michael Jäger
  • Prof. Dr. Hans-Rudolf Metz
  • Prof. Dr. 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”.

  • 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
Instruction Language
Total Effort
6.0 CrP; an estimated 180 hours, of which approximately 60 are spent in class.
Weekly School Hours
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)
  • M. Sipser: Introduction to the Theory of Computation
  • J. Hopcroft, R. Motwani, J. Ullman: Einführung in Automatentheorie, Formale Sprachen und Berechenbarkeit
Prerequisite Modules