Theory of Computation II

Overview

Regular languages:Introduction: Scope of study as limits to compubality and tractability - Why it suffices to consider only decision problems, equivalently, set membership problems. Notion of a formal language - DFAs and notion for their acceptance, informal and then formal definitions. Class of regular languages - Closure of the class under complementation, union and intersection. Strategy for designing DFAs - Pumping lemma for regular languages. Its use as an adversarial game - Generalized version. Converses of lemmas do not hold - NFAs. Notion of computation trees. Definition of languages accepted. Construction of equivalent DFAs of NFAs. NFAs with epsilon transitions. Guess and check paradigm for design of NFAs - Regular expressions. Proof that they capture precisely class of regular languages. Closure properties of and decision problems for regular languages - Myhill-Nerode theorem as characterization of regular languages.States minimization of DFAs

Context free languages:Notion of grammars and languages generated by grammars. Equivalence of regular grammars and finite automata. Context free grammars and their parse trees. Context free languages. Ambiguity - Pushdown automata (PDAs): deterministic and nondeterministic. Instantaneous descriptions of PDAs.Language acceptance by final states and by empty stack. Equivalence of these two - PDAs and CFGs capture precisely the same language class - Elimination of useless symbols, epsilon productions, unit productions from CFGs. Chomsky normal form - Pumping lemma for CFLs and its use. Closure properties of CFLs. Decision problems for CFLs - Turing machines, r.e. languages, undecidability - Informal proofs that some computational problems cannot be solved - Turing machines (TMs), their instantaneous descriptions. Language acceptance by TMs. Hennie convention for TM transition diagrams.Robustness of the model-- equivalence of natural generalizations as well as restrictions equivalent to basic model. Church-Turing hypothesis and its foundational implications - Codes for TMs. Recursively enumerable (r.e.) and recursive languages. Existence of non-r.e. languages. Notion of undecidable problems. Universal language and universal TM. Separation of recursive and r.e. classes. Notion of reduction. Some undecidable problems of TMs. Rice's theorem - Undecidability of Post's correspondence problem (PCP), some simple applications of undecidability of PCP;Intractability:Notion of tractability/feasibility. The classes NP and co-NP, their importance. Polynomial time many-one reduction - Completeness under this reduction. Cook-Levin theorem: NP-completeness of propositional satisfiability, other variants of satisfiability - NP-complete problems from other domains: graphs (clique, vertex cover, independent sets, Hamiltonian cycle), number problem (partition), set cover