Syllabus

Introduction: Notion of formal language. Language membership problem, why this is taken as the central problem of the subject. Finite automata and regular expressions: DFA, NFA (with and without transitions), their equivalence. Proof that FAs recognize, and regular expressions denote the same class of languages, viz., regular languages. Properties of regular languages: Pumping lemma and its use to prove non-regularity of a language, closure properties of class of regular languages, decision properties: converting among representations, testing emptiness, etc. Minimization of DFAs, Myhill-Nerode theorem. Context-free grammars and languages: Derivation, parse trees. Language generated by a CFG. Eliminating useless symbols, -productions, unit productions. Chomsky normal form.

Pushdown automata: Definition, instantaneous description as a snapshot of PDA computation, notion of acceptance for PDAs: acceptance by nal states, and by empty stack; the equivalence of the two notions. Proof that CFGs generate the same class of languages that PDAs accept. Properties of context-free languages: Pumping lemma for context-free languages and its use to prove a language to be not context-free. Closure properties of the class of context- free languages. CYK algorithm for CFL membership, testing emptiness of CFLs. Turing machines: Historical context, informal proofs of undecidability. Definition of TM, instantaneous description as a snapshot of TM computation, notion of acceptance. Robustness of the model. Church-Turing hypothesis. Undecidability: Definitions of r.e. and recursive languages. Turing machine codes, the diagonalization language and proof that it is not r.e. Universal Turing machine. Universal language, its semi-decidability. Reducibility and its use in proving undecidability. Rices theorem. Undecidability of Posts correspondence problem. Intractability: Motivation for the notion. The class P as consensus class of tractable sets. Classes NP, co-NP. Polynomial time reductions. NP-completess, NP-hardness. Cook-Levin theorem. Mention about boundary of tractability: 2SAT vs. 3SAT, 2D matching vs. 3D matching. Some NP-completeness proofs: vertex cover, clique, independent sets, Hamiltonian graphs, subset-sum, set cover.