Content

This course (usually offered in semester 1 in even years, in 2023 it’s offered additionally for the first time) covers the theoretical computer science areas of formal languages and automata, computability and complexity. Topics covered include:

  • regular and context-free languages;
  • finite automata and pushdown automata;
  • Turing machines;
  • Church’s thesis;
  • computability - halting problem, solvable and unsolvable problems;
  • space and time complexity;
  • classes P, NP, NP-Completeness, and PSPACE.

At successful completion of the course, students should have a good knowledge of formal computation and its relationship to languages, be able to classify formal languages into their types, be able to formally reason about languages, and understand the basic concepts of computability and complexity theory.

Note that this public webpage only contains “static knowledge” that won’t change during the semester. All data, information, news, etc. that’s year-dependent will be made available via Wattle. So you won’t miss anything if you carefully check out this public webpage once, and then stick to Wattle afterwards.

If you’re stuck, then you can reach out for help anytime—the course help page or course forum is a good place to start.

bars search times arrow-up