Theory of Computation. Instructor: Prof. Raghunath Tewari, Department of Computer Science and Engineering, IIT Kanpur.
FREE
This course includes
Hours of videos
1138 years, 9 months
Units & Quizzes
41
Unlimited Lifetime access
Access on mobile app
Certificate of Completion
This is an introductory course on Theory of Computation intended for undergraduate students in computer science. In this course we will introduce various models of computation and study their power and limitations. We will also explore the properties of the corresponding language classes defined by these models and the relations between them. We will assume the student is comfortable in analytical reasoning and has preferably done a course on Data Structures and Algorithms. (from nptel.ac.in)
Course Currilcum
- Lecture 01 – Introduction to Finite Automata Unlimited
- Lecture 02 – Basic Notation and Convention, DFA (Deterministic Finite Automaton) Edit Lesson Unlimited
- Lecture 03 – Examples of DFAs Unlimited
- Lecture 04 – Computation by DFA and Regular Operation Unlimited
- Lecture 05 – Introduction to Nondeterminism Unlimited
- Lecture 06 – NFA (Nondeterministic Finite Automaton), Definition and Examples Unlimited
- Lecture 07 – Equivalence of NFA and DFA, Closure Properties Unlimited
- Lecture 08 – Regular Expressions Unlimited
- Lecture 09 – Algebraic Properties, Regular Expression to NFA Conversion Unlimited
- Lecture 10 – Generalized NFA (GNFA) to Regular Expression Conversion Unlimited
- Lecture 11 – More Closure Properties of Regular Languages Unlimited
- Lecture 12 – Non-regular Languages and Pumping Lemma Unlimited
- Lecture 13 – Examples of Non-regular Languages Unlimited
- Lecture 14 – DFA Minimization Unlimited
- Lecture 15 – Introduction to Context Free Grammars (CFGs) Unlimited
- Lecture 16 – Examples of Context Free Grammars, Reg Subset of Context Free Languages Unlimited
- Lecture 17 – Parse Tree, Derivation, Ambiguity Unlimited
- Lecture 18 – Normal Forms, Chomsky Normal Form Unlimited
- Lecture 19 – Non-CFLs, Pumping Lemma Unlimited
- Lecture 20 – Examples of Non-CFLs Unlimited
- Lecture 21 – Pushdown Automata Unlimited
- Lecture 22 – Pushdown Automata – Definition and Example Unlimited
- Lecture 23 – Pushdown Automata – Examples and Relation with CFGs Unlimited
- Lecture 24 – Closure Properties of CFLs Unlimited
- Lecture 25 – Deterministic Context Free Languages Unlimited
- Lecture 26 – Turing Machine Unlimited
- Lecture 27 – More on Turing Machine Unlimited
- Lecture 28 – Non-deterministic Turing Machine Edit Lesson Unlimited
- Lecture 28 – Non-deterministic Turing Machine Edit Lesson Unlimited
- Lecture 29 – Configuration Graphs Unlimited
- Lecture 30 – Closure Properties of Decidable and Turing Recognizable Languages Unlimited
- Lecture 31 – Decidability Properties of Regular and Context Free Languages Unlimited
- Lecture 32 – Undecidability Unlimited
- Lecture 33 – More on Undecidability Unlimited
- Lecture 34 – Reduction Unlimited
- Lecture 35 – Applications of Reduction Unlimited
- Lecture 36 – Rice’s Theorem Unlimited
- Lecture 37 – Introduction to Computational Complexity Theory Unlimited
- Lecture 38 – More on the Class NP Unlimited
- Lecture 39 – NP-Completeness Unlimited
- Lecture 40 – More on NP-Completeness Unlimited
