Introduction: Motivation for studying theory of computation, a quick overview of the subject. 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 for some languages NFAs can be exponentially more succinct than DFAs. Denition of regular expressions. 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: convert- ing 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: Denition, instantaneous description as a snapshot of PDA com- putation, 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. Denition of TM, instantaneous description as a snapshot of TM computation, notion of acceptance. Robustness of the model: both natural generalizations and restrictions keep the class of languages accepted invariant. (Generalizations: multi-track, multi-tape, nondeterministic, etc. Restrictions: semi-innite tape, counter machines). Church-Turing hypothesis.
Undecidability: Denitions 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.