Automata and Complexity
Formal languages, automata, grammars, computability theory, and complexity classes (P, NP, NP-complete). Finite automata, pushdown automata, Turing machines.
Learning objectives
The first part of the course, on automata and languages, covers: design finite automata and create regular expressions for a given regular language; apply algorithms to translate between finite automata, right-linear grammars, and regular expressions; apply algorithms to make automata deterministic and minimal; design pushdown automata and create context-free grammars for a given context-free language; use pumping lemmas to reason about whether a language is regular or context-free; apply algorithms for parsing context-free languages. The second part, on computability theory, covers: reason whether a given problem is decidable (computable) or undecidable; understand the classification of decidable problems in the complexity hierarchy (P, NP, EXP); reason about the complexity of a problem via reduction.
This course treats automata & formal languages and computability theory. The student gets acquainted with important notions and algorithms regarding formal languages, automata, grammars, compilers, computability, and complexity. This course addresses foundational questions in computer science: What can be computed? What are the limitations to what computers can do? How much time and memory does solving a problem require? What is a (programming) language? How can languages be recognized by computers (automata)? Which problems can be solved by what kinds of automata? This course conveys the important idea that certain problems cannot be solved by computers. A computer scientist must be able to reason whether a given problem is computable (decidable) or not. Moreover, a computer scientist should be able to reason what language/complexity class a given problem belongs to, and hence what kind of automata/algorithms are needed to tackle the problem.
Assessment
The homework is mandatory for qualifying for the exam (70% of the homework points to qualify for the exam). In case at least 90% of the homework points is obtained, 0.5 bonus point is awarded for the final grade. At the end of the course there is a final exam. The overall grade is the grade of the final exam plus the possibly 0.5 bonus point obtained for the homework. (The bonus is only added for students that pass the exam with a grade of at least 5.5.) There is no resit opportunity for the homework.
Teaching methods
4 hours per week lectures; 4 hours per week exercise classes.
Literature
Peter Linz, An Introduction to Formal Languages and Automata, Jones & Bartlett, 4th or 5th edition
Help us improve this page
Automata and Complexity
This course doesn't have detailed student info yet. Your tips, summaries, or resources would help everyone. You can submit materials anonymously — no account needed.
Submit materials
Upload summaries, notes & more
Or get in touch
Email us for quick changes, questions, or anything that isn't a large file.
Tip: Use the Canvas Course Downloader extension to export your course materials from Canvas, then upload the files through the form above.
You can also contribute via a GitHub pull request. Contributors are credited if desired.