Module Handbook

  • Dynamischer Default-Fachbereich geändert auf INF

Course INF-02-04-K-2

Formal Languages and Computability (3V+2U, 6.0 LP)

Course Type

SWS Type Course Form CP (Effort) Presence-Time / Self-Study
- K Lecture with exercise classes (V/U) 6.0 CP 110 h
3 V Lecture 42 h
2 U Exercise class (in small groups) 28 h
(3V+2U) 6.0 CP 70 h 110 h


CP, Effort 6.0 CP = 180 h
Position of the semester 1 Sem. in SuSe
Level [2] Bachelor (Fundamentals)
Language [DE] German
Area of study [INF-PFL] Mandatory Modules
Livecycle-State [NORM] Active

Possible Study achievement

  • Verification of study performance: proof of successful participation in the exercise classes (ungraded)
  • Details of the examination (type, duration, criteria) will be announced at the beginning of the course.


  • Definitions of language and different forms of representation of languages: Automata and machine models
  • Hierarchy of the languages generated/recognized by them and their power
  • Pumping lemmas
  • Computability models: simulation as a principle of comparison between computability models. The thesis of Church-Turing.
  • Holding problem
  • Functional programming languages (primitive and partially recursive functions)
  • Diagonalization technique, structural induction and reduction technique


  • Sperschneider, Hammer: Theoretische Informatik — Eine problemorientierte Einführung, Springer, 1996.
  • Hopcroft, Motwani, Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie, Addison Wesley, Pearson Studium, 2002.

References to Course [INF-02-04-K-2]

Module Name Context
[INF-02-04-M-2] Formal Languages and Computability P: Obligatory 3V+2U, 6.0 LP
[INF-82-59-M-2] Foundations of Theoretical Computer Science P: Obligatory 3V+2U, 6.0 LP