# InfoCoBuild

## Theory of Computation

Theory of Computation. Instructor: Prof. Somenath Biswas, Department of Computer Science and Engineering, IIT Kanpur. The objective of the course is to provide an exposition first to the notion of computability, then to the notion of computational feasibility or tractability. We first convince ourselves that for our purpose it suffices to consider only language recognition problems instead of general computational problems. We then provide a thorough account of finite state automata and regular languages, not only because these capture the simplest language class of interest and are useful in many diverse domains. We then consider context grammars and languages, and their properties. Next, we consider Turing machines (TMs). We then obtain the separation of the classes recursively enumerable, and recursive. A number of TM related problems are shown to be undecidable. Finally, we introduce the notion of feasible or tractable computation. (from nptel.ac.in)

 What is Theory of Computation?

 Lecture 01 - What is Theory of Computation? Lecture 02 - Introduction to Finite Automaton Lecture 03 - Finite Automata, Deterministic Finite Automata, Language Accepted by a DFA Lecture 04 - Regular Languages, their Closure Properties Lecture 05 - DFAs Solve Set Membership Problems in Linear Time, Pumping Lemma Lecture 06 - More Examples of Non-regular Languages, Proof of Pumping Lemma, Pumping Lemma as a Game Lecture 07 - A Generalization of Pumping Lemma, Nondeterministic Finite Automata, Computation Trees for NFAs Lecture 08 - Formal Description of NFA, Language Accepted by NFA Lecture 09 - Guess and Verify Paradigm for Nondeterminism Lecture 10 - NFAs with Epsilon Transitions Lecture 11 - Regular Expressions, They Denote Regular Languages Lecture 12 - Construction of a Regular Expression for a Language, Algebraic Closure Properties of Regular Languages Lecture 13 - Closure Properties (cont.) Lecture 14 - Closure under Reversal, Use of Closure Properties Lecture 15 - Decision Problems for Regular Languages Lecture 16 - Minimization of States of DFAs, Myhill-Nerode Theorem Lecture 17 - Continuation of Proof of Myhill-Nerode Theorem Lecture 18 - Application of Myhill-Nerode Theorem, DFA Minimization Lecture 19 - DFA Minimization (cont.) Lecture 20 - Introduction to Context Free Languages and Context Free Grammars Lecture 21 - Languages Generated by a CFG, Leftmost Derivation, Examples of CFGs and CFLs Lecture 22 - Parse Trees, Inductive Proof that L is L(G), All Regular Languages are Context Free Lecture 23 - Towards Chomsky Normal Forms Lecture 24 - Simplification of CFGs (cont.), Removal of Epsilon Productions Lecture 25 - Elimination of Unit Productions, Converting a CFG into Chomsky Normal Form Lecture 26 - Pumping Lemma for CFLs, Adversarial Paradigm Lecture 27 - Completion of Pumping Lemma Proof, Examples of Use of Pumping Lemma Lecture 28 - Closure Properties (cont.), CFLs not Closed under Complementation Lecture 29 - An Example of a CFL whose Complement is not a CFL, Decision Problems for CFLs Lecture 30 - More Decision Problems, CYK Algorithm for Membership Decision Lecture 31 - Introduction to Pushdown Automata (PDA) Lecture 32 - PDA Configurations, Acceptance Notions for PDAs, Transition Diagrams for PDAs Lecture 33 - Equivalence of Acceptance by Empty Stack and Acceptance by Final State Lecture 34 - Turing Machines (TM): Motivation, Informal Definition, Example Lecture 35 - Execution Trace, Example of Unary to Binary Conversion Lecture 36 - Finiteness of TM Description, TM Configuration, Language Acceptance Lecture 37 - Notion of Non-acceptance or Rejection of a String by a TM, Multitrack TM Lecture 38 - Simulation of Multitape TMs by Basic Model, Nondeterministic TM, Equivalence of NDTMs with Deterministic TMs Lecture 39 - Counter Machines and their Equivalence to Basic TM Model Lecture 40 - TMs can Simulate Computers, Diagonalization Proof Lecture 41 - Existence of Non-recursively Enumerable Languages, Recursive Languages, Notion of Decidability Lecture 42 - Separation of Recursive and Recursively Enumerable Classes, Halting Problem and its Undecidability

 References Theory of Computation Instructor: Prof. Somenath Biswas, Department of Computer Science and Engineering, IIT Kanpur. The objective of the course is to provide an exposition first to the notion of computability, then to the notion of computational feasibility or tractability.