de | en

Introduction to Theory of Computation

Module IN0011

This Module is offered by TUM Department of Informatics.

This module handbook serves to describe contents, learning outcome, methods and examination type as well as linking to current dates for courses and module examination in the respective sections.

Basic Information

IN0011 is a semester module in German language at Bachelor’s level which is offered in summer semester.

Total workloadContact hoursCredits (ECTS)
240 h 90 h 8 CP

Content, Learning Outcome and Preconditions

Content

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.

Learning Outcome

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.

Preconditions

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

Courses, Learning and Teaching Methods and Literature

Courses and Schedule

Learning and Teaching Methods

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

Media

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

Literature

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.

Module Exam

Description of exams and course work

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.

Exam Repetition

The exam may be repeated at the end of the semester.

Top of page