Learn · NPTEL

Course10610414839 lectures

Theory of Computation

Prof. Raghunath Tewari · IIT Kanpur

Start with lecture 1 At NPTEL

About

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.

Intended audience: Computer Science undergraduate students.

Prerequisites: It is recommended that the candidate has done a course in Data Structures and Algorithms.

Lectures

Week 1

  1. Introduction to Finite Automata YouTube
  2. Basic Notation and Convention, DFA YouTube
  3. Example of DFAs YouTube
  4. Computation by DFA and Regular operation YouTube
  5. Introduction to Nondeterminism YouTube

Week 2

  1. NFA, definition and examples YouTube
  2. Equivalence of NFA and DFA, Closure properties YouTube
  3. Regular expressions YouTube
  4. Algebraic properties, RE to NFA conversion YouTube
  5. GNFA to RE conversion YouTube

Week 3

  1. More closure properties of regular languages YouTube
  2. Non-regular languages and pumping lemma YouTube
  3. Examples of non-regular languages YouTube
  4. DFA minimization YouTube
  5. Introduction to CFGs YouTube

Week 4

  1. Examples of CFGs, Reg subset of CFL YouTube
  2. Parse tree, derivation, ambiguity YouTube
  3. Normal forms, Chomsky normal form YouTube
  4. Non-CFLs, pumping lemma YouTube
  5. Examples of non- CFLs YouTube

Week 5

  1. Pushdown Automata YouTube
  2. Pushdown Automata - Definition and Example YouTube
  3. Pushdown Automata - Examples and Relation with CFGs YouTube
  4. Closure Properties of CFLs YouTube
  5. Deterministic Context Free Languages YouTube

Week 6

  1. Turing Machine YouTube
  2. More on Turing Machine YouTube
  3. Non deterministic Turing Machine YouTube
  4. Configuration Graphs YouTube

Week 7

  1. Decidability properties of Regular and Context Free Languages YouTube
  2. Undecidability YouTube
  3. More on Undecidability YouTube
  4. Reduction YouTube
  5. Applications of Reduction YouTube

Week 8

  1. Rice's theorem YouTube
  2. Introduction to Computational Complexity Theory YouTube
  3. More on the class NP YouTube
  4. NP-Completeness YouTube
  5. More on NP-Completeness YouTube

Syllabus and materials

At NPTEL, as the course publishes them.

Credits and licence

Institution
IIT Kanpur
Department
Computer Science and Engineering
Teacher
Prof. Raghunath Tewari
Level
Undergraduate
Language
English
Subjects
Computer science, Engineering
Source
NPTEL
Licence
CC BY-NC-SA, as NPTEL states it. Non-commercial use only. NPTEL's terms
Attribution
NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge.
Who can watch
NPTEL gives no rating. Invisible Network shows it to Tweens profiles and older, judged from what the source says about it. How courses are placed