Automata & Complexity

In 2013-2014 I am teaching the course on automata & complexity, in which students can familiarise themselves with important concepts and algorithms in formal languages, automata, grammars, compilers, computability, and complexity.

I discuss the following topics: regular languages, finite automata, context free languages, pushdown automata, LL and LR parsing, the JFLAP tool, Turing machines, context-sensitive languages, undecidable problems, complexity classes P and NP, NP-completeness, Cook’s theorem, complexity class PSPACE, Savitch’s theorem, quantum computing and quantum-cryptography.

The home page for the course can be found on the TCS home page.