Theory of Computation

(09-03-2021) -- Lecture 1

Course Introduction, Motivation, and Course Structure - Lecture 1

(15-03-2021) -- Lecture 2

Proof Techniques: Direct proof and Indirect Proof - Lecture 2

(17-03-2021) -- Lecture 3

Mathematical Induction - Lecture 3

(18-03-2021) -- Lecture 4

Mathematical Logic: Propositional Logic - Lecture 4

(22-03-2021) -- Lecture 5

Mathematical Logic: First Order Logic - Lecture 5

(24-03-2021) -- Lecture 6

Computability Theory: Automaton, Formal Languages, and Language Operations - Lecture 6

(26-03-2021) -- Lecture 7

Introduction to Finite Automata - Lecture 7

(29-03-2021) -- Lecture 8

Finite Automata Continued, Language of a FA, Designing a FA, Types of FA - Lecture 8

(31-03-2021) -- Lecture 9

Deterministic Finite Automata, Language of a DFA, Closure Properties - Lecture 9

(02-04-2021) -- Lecture 10

DFA, Transition Table, Non-Deterministic Finite Automata, Language of an NFA - Lecture 10

(06-04-2021) -- Lecture 11

DFA, Epsilon NFA, Powerset or Subset construction - Lecture 11

(08-04-2021) -- Lecture 12

Closure Properties and Decision Problems for Finite Automata - Lecture 12

(12-04-2021) -- Lecture 13

DFA Minimization - Lecture 13

(14-04-2021) -- Lecture 14

Regular Expressions - Lecture 14

(16-04-2021) -- Lecture 15a

Regular Expression to Finite Automata Conversion - Lecture 15a

(19-04-2021) -- Lecture 15b

Finite Automata to Regular Expression Conversion - Lecture 15b

(21-04-2021) -- Lecture 16

MyHill Nerode Theorem for Non Regular Languages - Lecture 16

(23-04-2021) -- Lecture 17

Pumping Lemma for Non Regular Languages - Lecture 17

(27-04-2021) -- Lecture 18

Introduction to Grammars - Lecture 18

(10-05-2021) -- Lecture 19

Context Free Grammars - Lecture 19

(12-05-2021) -- Lecture 20

Classification of Context-Free Grammars - Lecture 20

(17-05-2021) -- Lecture 21

Simplification of Context-Free Grammars - Lecture 21

(19-05-2021) -- Lecture 22

Chomsky Normal Form and Greibach Normal Form - Lecture 22

(21-05-2021) -- Lecture 23

Pumping Lemma for Context Free Languages - Lecture 23

(24-05-2021) -- Lecture 24

Closure Properties of Context Free Languages - Lecture 24

(26-05-2021) -- Lecture 25

PushDown Automata - Lecture 25

(28-05-2021) -- Lecture 26

Acceptance by a PushDown Automata, Deterministic and Non Deterministic PDA - Lecture 26

(31-05-2021) -- Lecture 27

Decision Problems for CFLs - Lecture 27

(02-06-2021) -- Lecture 28

Turing Machines - Lecture 28

(04-06-2021) -- Lecture 29

Designing TMs, TM as a subroutine - Lecture 29

(07-06-2021) -- Lecture 30

Power of Turing Machines - Lecture 30

(09-06-2021) -- Lecture 31

Recognizer and Decider, R and RE Languages - Lecture 31

(14-06-2021) -- Lecture 32

R and RE Languages, Universal Turing Machine - Lecture 32

(16-06-2021) -- Lecture 33

Halting Problem, Decidable and Undecidable Languages - Lecture 33