Introduction to Theory of Computation
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.
IN0011 is a semester module in German language at Bachelor’s level which is offered in summer semester.
|Total workload||Contact hours||Credits (ECTS)|
|240 h||90 h||8 CP|
Content, Learning Outcome and Preconditions
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.
Courses, Learning and Teaching Methods and Literature
Courses and Schedule
|VO||4||Introduction to Theory of Computation (IN0011)||
|UE||2||Introduction to Theory of Computation, Exercise Session (IN0011)|
Learning and Teaching Methods
Dexter Kozen. Automata and Computability
Katrin Erk, Lutz Priese. Theoretische Informatik. Eine umfassende Einführung.
Uwe Schöning. Theoretische Informatik kurzgefasst.
Description of exams and course work
The exam may be repeated at the end of the semester.