Automata and Computability



  • 2013 Autumn/Monsoon (Aug - Dec)

The objective of the course is to provide a rigorous treatment of the classical automata and computability theory, and to explore its role in current day computer science.


Introduction to automata and computability: a historical overview and relevance. Mathematical Preliminaries: Sets, relations and partial orders, countability, Methods of proof, Structural and Noetherian Induction.

Finite State Automata: DFA,NFA, epsilon-NFA and their equivalence. Regular expressions and their equivalence to DFA. Moore and Mealy Machines. Closure properties of regular languages. Decision Problems: membership, nonemptiness, language containment, finiteness. Equational Axioms for Regular Expressions, Pumping Lemma, Minimization of DFA, Myhill-Nerode Theorem.

Context-free Langauges and Pushdown Automata: Context-free grammers, Normal forms, Pumping Lemma, Pushdown Automata. Equivalence of CFG and Pushdown Automata. Membership problem and parsing. Closure properties and decision problems.

Turing Machines and Undecidability: Turing machines. Robustness. Closure properties. Universal Turing Machine. Recursive and RE langauges. Undecidability of Halting Problem. Many-to-one reductions and Rice’s Theorem. Chomsky Hierarchy. Alternative models of computation.

Advanced Topics.

Textbook: Dexter Kozen, Automata and Computability, Springer, 1997.

Course Grading: The emphasis will be on problem solving and learning to write rigorous proofs for the results. There will be assignments and tutorials. ​

  1. End semester exam, which will be based on assignments, will carry 50% marks.
  2. Each student will be expected to give two seminars on some advanced topics of their choice. The two seminars together will carry 50% marks.

Past seminar topics: Two way finite state automata, alternating finite state automata, bisimulation and collapsing nondeterministic automata, Chomsky-Schutzenberger Theorem and Parikh Theorem for CFL, Beyond Undecidabillity: an arithmetic hierarchy of undecidable problems. Godel's incompleteness theorem. Alternative models of computation and their equivalence with turing machines.