Theory of Computation
Instructor
Dr. Janibul Bashir
Course Overview
In this course, we'll study the different solvable and unsolvable problems. We will understand why some problems are called hard problems. We will also discuss the different computational models to solve different type of problems.
Course Code
IT E20
Lectures
Online
Text Book (TB): Introduction to the Theory of Computation by Michael Sipser
Video Lectures: Theory of Computation
Course Content
Chapter 1 (Introduction)
(09-03-2021) -- Lecture 1
Course Introduction, Motivation, and Course Structure - Lecture 1
Chapter 2 (Mathematical Preliminaries)
Chapter 3 (Computability Theory - Finite Automata)
(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
Chapter 4 (Grammars - Context Free Grammars)
(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
Chapter 5 (Turing Machines)
(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