Automata and formal Languages

Short Name
Automaten u. formale Spr
Module Code
CS2315
Module Coordinator
  • Prof. Dr. Albert Schneider
Teacher
  • 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”.

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