Automata and Computability



  • 2012 Autumn/Monsoon (Aug - Dec)

Introduction Languages and language recognition problem. Computability:
Historical overview.

Mathematical Preliminaries Sets and relations, countability, Methods of
proof, Structural and Moetherian Induction.

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

Context-free Langauges and Pushdown Automata Context-free gram-
mers, 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. Clo-
sure properties. Universal Turing Machine. Recursive and RE langauges. Un-
decidability of Halting Problem. Many-to-one Reductions and Rice’s Theorem.
Chomsky Hierarchy.

• Dexter Kozen, Automata and Computability, Springer, 1997.
• Hopcroft and Ullman, Introduction to Automata theory, Langauges and
Computations, Narosa Publishing House, India (1993).