Theory of Computation

What you’ll study

Language theory; finite automata — deterministic finite automata, nondeterministic finite automata, the equivalence and conversion of deterministic and nondeterministic finite automata, pushdown automata; regular expressions and their properties; the Chomsky hierarchy, regular grammar and regular language; context-free languages and context-free grammars; the pumping lemma and its applications; Turing machines — basic machines, configuration, computing with Turing machines and combining Turing machines; the Mealy machine and the Moore machine; undecidability — the diagonalization method, the halting problem, undecidable problems from language theory and reducibility; the recursion theorem.