After successful completion of the course, students are able to understand the fundamental concepts and results of automata theory and formal languages, computability and complexity theory, as well as the formal semantics of programming languages. The students possess the ability to read and comprehend formal descriptions and describe concepts in a formal-mathematical manner. They understand the structure of proofs and arguments and are able to conduct such reasoning themselves. In particular, the students understand the abstract concept of problem reductions, and are able to conduct reduction proofs in the contexts of the course. They are capable of  addressing and solving questions within the scope of theoretical computer science on their own. Additionally, the students are able to identify, formulate, and discuss ethical issues in the context of this course.

The course covers the fundamental concepts and results of the following areas.

Automata theory: deterministic and indeterministic automata, push-down automata, Turing machines
Formal languages: regular and context-free languages, Chomsky hierarchy
Computability and complexity: universal computability, complexity classes like undecidability and NP-completeness
Formal semantics of programming languages: operational and axiomatic semantics

Twice a week, the course contents are presented in the lecture hall, and relevant exercises and examples are discussed. Throughout the semester, students work on four sets of exercises covering the topics. One to two weeks after submitting their solutions, students receive feedback on the correctness of their attempts and access to model solutions. Questions are answered after the lecture, online in the TUWEL forum, via email, and during separate Q&A sessions.

Ects Breakdown

 50h presentations/exercises in the lecture hall
 50h exercise sheets
 50h preparation for final tests
------------------------------------------------
150h = 6.0 Ects

The final grade is determined on the basis of  the submitted exercises (four sheets, 40 points in total) and the written final test (60 points), giving a grand total of 100 points. To pass the course you need at least 30 points on the written test and at least 50 points in total. Positive grades are determined from the sum of points according to the following scale:

• 50-61 points: passed (4)
• 62-74 points: satisfactory (3)
• 75-87 points: good (2)
• 88-100 points: excellent (1)

Basic knowledge of mathematical argumentation, algorithmics and formal specification with automata and formal languages.