Introduction to Theory of Computation

Formal languages, grammars, Chomsky hierarchy.

Regular languages: DFA, NFA with and without ε-transitions, regular expressions and translations between them; systems of language equations; closure under boolean operations; Arden’s lemma; pumping lemma; decision problems; minimization; Myhill-Nerode theorem.

CFLs: PDAs and translation between CFGs and PDAs; proof that DPDAs are weaker than PDAs; closure properties; CYK algorithm; pumping lemma; Chomsky and Greibach normal forms.

Context-sensitive languages and LBAs.

Computability: computability, decidability, semi-decidability, recursive-enumerability and their relationships; existence of non-computable problems; Turing machines, accepted languages, type-0 languages: equivalence of Turig machines, While-programs and Goto-programs; primitive and µ-recursive functions; reductions between problems; the Halting problem; universal Turing machines; Rice’s theorem; Rice-Shapiro theorem; undecidability of the Post Correspondence Problem and important problems on CFGs.

Complexity theory: time and space complexity classes; polynomial-time reductions; the classes P and NP; NP-completeness; Cook’s theorem; important NP-complete problems and reductions between them.

All proofs are covered.

After successfully completing this module, the students understand the core concepts of the theory of computation on a basic but scientific level. They know what regular expressions, contextfree grammars, the Chomsky hierarchy, finite automata and Turing machines are. They can define formal languages with the appropriate grammars or machines. They can prove that a given language cannot be defined with a given class of grammars or machines. They can prove that certain grammars and machines are equivalent and they can transform them into each other algorithmically. They can explain the basic concepts of complexity theory and can reduce decision problems algorithmically to each other under given complexity limitations.

IN0015 Discrete Structures, MA0901 Linear Algebra for Informatics, MA0902 Analysis for Informatics

The module consists of lectures and exercises. In the lectures, the material is presented by the teacher, in dialogue with the students. During the exercises, the students work on given exercises either individually or in small groups with help from the supervisors. Exercises and homework are primarily pen and paper based but can also involve computer-based components.

Lecture notes, slides, blackboard, animations, video recordings, online exercises and homework assignments, online discussion forum

John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation
Dexter Kozen. Automata and Computability
Katrin Erk, Lutz Priese. Theoretische Informatik. Eine umfassende Einführung.
Uwe Schöning. Theoretische Informatik kurzgefasst.

The exam takes the form of a 180 minutes written test. Knowledge questions allow to assess acquaintance with concepts of Theoretical Informatics, algorithmic questions assess the ability to apply known algorithms to concrete problems or to design small new algorithms, and deductive questions assess the ability to reason logically about the concepts of the course.