# Theoretical Computer Science

Undergraduate / Graduate Course, *Ruhr University Bochum*, 2022

- Lecturer: Prof. Dr. Zeume
- Language: German
- Credits: 8 CP
- Programs: B.Sc. Applied Computer Science, B.Sc. Computer Science, B.Sc. IT-Security, B.Sc./M.Sc. Mathematics
- Examination: 100 % Written Exam (120 Minutes) + 10 % Homework / 100 % Oral Exam (30 Minutes)

# Course Description

The lecture is intended for students of mathematics, computer science, applied computer science and IT security. It provides an introduction to the theory of grammars (especially context-free grammars) and automata (finite state automaton, pushdown automaton, Turing machine). It will also give an insight into computability and NP-comleteness theory, where the question is which computational problems can be solved (at all or with reasonable effort). It will be shown that there are inherently hard problems that cannot be solved satisfactorily by computers. The lecture will yiels fundamental insights into the relationship between automata and grammars and the relationship between determinism and non-determinism. By practicing techniques such as mutual simulation or (polynomially) computable reductions, the insight should mature that concepts that look different on the surface can be identical at the core. The goal is also deeper understanding of complexity. On the lower levels of the so-called Chomsky hierarchy one finds efficiently solvable application problems of text manipulation and text analysis. On the upper levels, on the other hand, one encounters the phenomenon of the inherent hardness (or even undecidability) of a problem.

# Contents

Part A: Regular Languages

- Regular Expressions and Languages
- Finite Automata
- Equivalence of the models
- Minimizing automata
- Properties of regular languages
- Applications and Extensions Part B: Context-free Languages
- Context-Free Grammar
- Normal forms and proofs of correctness
- Pushdown automata
- Properties of context-free languages
- Membership problem and Syntax analysis Part C: Computability
- Turing machines
- Church-Turing thesis
- Undecidability of Halting problem
- Undecidable problems
- Further Variations and Results Part D: Computational complexity theory
- Polynomial Time
- NP and NP-Completeness
- First NP-complete problems
- Further NP-complete problems
- Dealing with NP-complete problems
- Algorithms for SAT and Exponential Time Hypothesis
- Random-based complexity classes