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