## Instructor:

## Semester:

- 2012 Autumn/Monsoon (Aug - Dec)

Syllabus

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.

Textbooks

• Dexter Kozen, Automata and Computability, Springer, 1997.

• Hopcroft and Ullman, Introduction to Automata theory, Langauges and

Computations, Narosa Publishing House, India (1993).