|
Module 1 - Regular Languages & Finite Automata
|
|
|
|
About Lecture 1
|
|
|
|
TOC Lecture 1 - What is Theory of Computation
|
|
|
|
Notes 1 - TOC Lecture 1 - What is Theory of Computation
(106 pages)
|
|
|
|
Lecture 2 - Basic Concepts of Automata Theory
|
|
|
|
Lecture 3 - Basic Concepts Part 2
|
|
|
|
Notes 2,3 - TOC Lecture 2,3 - Basic Concepts Annotated Notes
(261 pages)
|
|
|
|
Lecture 4 - Complement of language & Automata
|
|
|
|
Lecture 5 - Finite Automata Introduction
|
|
|
|
Notes 4,5 - TOC Lecture 4,5 - Finite Automata Introduction Annotated Notes
(89 pages)
|
|
|
|
Lecture 6 - Finite Automata Definition
|
|
|
|
Lecture 7 - Deterministic Finite Automata
|
|
|
|
Notes 6,7 - TOC Lecture 6,7 - Deterministic Finite Automata Annotated Notes
(168 pages)
|
|
|
|
Lecture 8 - Designing DFAs
|
|
|
|
Lecture 9 - Designing DFAs Part 2
|
|
|
|
Notes 8,9 - TOC Lecture 8,9 - Designing DFA Annotated Notes
(156 pages)
|
|
|
|
Lecture 10 - The Product Construction
|
|
|
|
Notes 10 - TOC Lecture 10 - The Product Construction Annotated Notes
(124 pages)
|
|
|
|
Lecture 11 - Minimization of DFA, Equivalent States
|
|
|
|
Lecture 12 - DFA Minimization, Partition Algorithm
|
|
|
|
Notes 11,12 - TOC Lecture 11,12 - Minimization of DFA Annotated Notes
(182 pages)
|
|
|
|
Lecture 13 - NFA Non-Deterministic Finite Automata
|
|
|
|
Lecture 14 - Designing NFAs
|
|
|
|
Notes 13,14 - TOC Lecture 13,14 - NFA Annotated Notes
(132 pages)
|
|
|
|
Lecture 15 - NFA with Null Moves
|
|
|
|
Lecture 16 - NFA to DFA Conversion
|
|
|
|
Notes 15,16 - TOC Lecture 15,16 - Null Moves, NFA to DFA Conversion Annotated Notes
(176 pages)
|
|
|
|
Lecture 17 - A note on NFAs
|
|
|
|
Lecture 18- Regular Expression Introduction
|
|
|
|
Notes 17,18 - TOC Lecture 17,18 - Regular Expressions Annotated Notes
(148 pages)
|
|
|
|
Lecture 19 - Understanding Regular Expressions
|
|
|
|
Lecture 20 - Writing Regular Expressions
|
|
|
|
Notes 19,20 - TOC Lecture 19,20 - Regular Expressions Annotated Notes
(149 pages)
|
|
|
|
Lecture 21 - Important Properties of Regular Expressions
|
|
|
|
Notes 21 - Lecture 21 - Important Properties of Regular Expressions Annotated Notes
(80 pages)
|
|
|
|
Lecture 22 - Equivalence of FA and RE
|
|
|
|
Notes 22 - Lecture 22 - Equivalence of FA and RE Annotated Notes
(84 pages)
|
|
|
|
Lecture 23 - FA to RE Conversion
|
|
|
|
Lecture 24 - FA to RE Conversion - The Two Templates
|
|
|
|
Notes 23,24 - Lecture 23,24 - FA to RE Conversion Annotated Notes
(156 pages)
|
|
|
|
Next Topic: Pumping Lemma for Regular Languages
|
|
|
|
Lecture 25 - Pumping Lemma for Regular Languages
|
|
|
|
Notes 25 - Lecture 25 Pumping Lemma for Regular Languages Annotated Notes
(222 pages)
|
|
|
|
Lecture 26 - Non-Regular Languages
135:00
|
|
|
|
Notes 26 - Lecture 26 - Non-regular languages Annotated Notes
(142 pages)
|
|
|
|
Lecture 27 - Distinguishable Strings, Non-Regular Languages
116:00
|
|
|
|
Lecture 28 - Myhill Nerode Theorem & Non-Regular Languages
51:00
|
|
|
|
Notes 27,28 - Lecture 27,28 - Myhill Nerode Theorem & Non-Regular Languages Annotated Notes
(159 pages)
|
|
|
|
Lecture 29 - Myhill Nerode Equivalence Relation
|
|
|
|
Notes 29 - Lecture 29 - Myhill Nerode Equivalence Relation Annotated Notes
(106 pages)
|
|
|
Module 2 - Context Free Languages, Grammars, Pushdown Automata
|
|
|
|
Lecture 30 - Context Free Grammars
|
|
|
|
Notes 30 - Lecture 30 - Context Free Grammars Annotated Notes
(117 pages)
|
|
|
|
Lecture 31 - Practice & Examples of CFGs
|
|
|
|
Notes 31 - Lecture 31 - Practice & Examples of CFGs Annotated Notes
(105 pages)
|
|
|
|
Lecture 32 - Linear Grammar, Regular Grammar, Right Linear Grammar to Finite Automata
59:00
|
|
|
|
Notes 32 - Lecture 32 - Linear Grammar, Regular Grammar, Right Linear Grammar to Finite Automata Annotated Notes
(59 pages)
|
|
|
|
Lecture 33 - Ambiguity of Context Free Grammar | Left Linear Grammar
207:00
|
|
|
|
Notes 33 - Lecture 33 - Ambiguity of Grammars Annotated Notes
(156 pages)
|
|
|
|
Lecture 34 - Push Down Automata
|
|
|
|
Lecture 35 - PDA Design
|
|
|
|
Notes 34,35 - Lecture 34,35 - Push Down Automata Annotated Notes
(144 pages)
|
|
|
|
Lecture 36 - PDA Analysis | Understanding PDA Transitions | Understanding Non-Determinism
42:00
|
|
|
|
PDA Design Example 1 - a^nb^n Language
|
|
|
|
PDA Design Example 2 - a^nb^n+1 Language
12:00
|
|
|
|
PDA Design Example 3 - a^nb^m Language
11:00
|
|
|
|
PDA Design Example 4 - a^nb^m Language
7:00
|
|
|
|
PDA Design Example 5 - a^nb^m Language
13:00
|
|
|
|
PDA Design Example 6 - a^nb^2n Language
14:00
|
|
|
|
PDA Design Example 7 - a^2nb^n Language
17:00
|
|
|
|
Notes 36 - Lecture 36 - PDA Design Examples, Understanding PDA Transitions Annotated Notes
(107 pages)
|
|
|
|
Lecture 37 - PDA Design More Examples
|
|
|
|
Lecture 38 - PDA Analysis, Definition, Empty Stack Acceptance
|
|
|
|
Notes 37,38 - TOC Lecture 37,38 - PDA Design, Definition, Empty Stack Acceptance Annotated Notes
(213 pages)
|
|
|
|
Lecture 39 - PDA with Empty Stack & Introduction to DPDA
|
|
|
|
Lecture 40 - DPDAs & DCFLs
|
|
|
|
Notes 39,40 - Lecture 39,40 - DPDAs & DCFLs Annotated Notes
(212 pages)
|
|
|
|
Lecture 41 - Detection of Language Classes - Regular Language Identification
|
|
|
|
Notes 41 - Lecture 41 - Detection of Language Classes - Regular Language Identification Annotated Notes
(128 pages)
|
|
|
|
Lecture 42 - Detection of DCFL, CFL Language Classes
|
|
|
|
Lecture 43 - Identification of Language Class Part 3
|
|
|
|
Notes 42,43 - Lecture 42,43 - Detection of DCFL, CFL Language Classes Annotated Notes
(205 pages)
|
|
|
|
Lecture 44 - Closure Properties of Regular Languages
80:00
|
|
|
|
Notes 44 - Lecture 44 Closure Properties Annotated Notes
(83 pages)
|
|
|
|
Lecture 45 - Closure Properties of CFLs
80:00
|
|
|
|
Lecture 46 - Closure Properties of CFLs, DCFLs, Non Regular Languages
85:00
|
|
|
|
Notes 45,46 - Lecture 45,46 Closure Properties Annotated Notes
(199 pages)
|
|
|
|
Closure Properties of Finite Languages
22:00
|
|
|
|
DCFLs are Not closed under Concatenation and Kleene Closure
14:00
|
|
|
|
GATE CS 1989 Q3 | Closure Properties of CFLs & Regular Languages
18:00
|
|
|
|
GATE CS 2020 Q8 - Regular languages NOT Closed under Infinite Union
12:00
|
|
|
|
Lecture 47 - Chomsky Hierarchy, Types of Grammars, Closure Properties Questions
85:00
|
|
|
|
Notes 47 - Lecture 47 - Chomsky Hierarchy Annotated Notes
(170 pages)
|
|
|
Module 3 - Turing Machines, Undecidability
|
|
|
|
Lecture 43 - Introduction of Turing Machines
|
|
|
|
Notes 43 - Lecture 43 - Introduction of Turing Machines Annotated Notes
(107 pages)
|
|
|
|
Lecture 44 - Turing Machines Design
|
|
|
|
Lecture 45 - Computability & Church-Turing Thesis
|
|
|
|
Notes 44, 45 - Lecture 44,45 - Computability & Church-Turing Thesis Annotated Notes
(330 pages)
|
|
|
|
Lecture 46 - Halting and Looping of TM | What does Infinite Loop Means?
|
|
|
|
Notes 46 - Lecture 46 Halting & Looping Annotated Notes
(151 pages)
|
|
|
|
Lecture 47 - Infinite Looping Revision
|
|
|
|
Lecture 48 - Decidability, Dovetailing
|
|
|
|
Notes 47,48 - Lecture 47,48 - Decidability, Dovetailing Annotated Notes
(253 pages)
|
|
|
|
Lecture 49 - Encoding, Decision Problems, Decidability
184:00
|
|
|
|
Notes 49 - Lecture 49 Encoding, Decision Problems, Decidability Annotated Notes
(116 pages)
|
|
|
|
Lecture 50 - Revision Lecture Turing Machine Behavior, Infinite Looping, Encoding of TM
131:00
|
|
|
|
Lecture 51 - Revision & Practice Encoding
|
|
|
|
Notes 51 - Lecture 51 - Revision & Practice Encoding Annotated Notes
(110 pages)
|
|
|
|
Lecture 52 - Decision Problems, Logical thinking of Undecidability
|
|
|
|
Lecture 53 - Logically Solving Decision Problems related to Language of TMs
|
|
|
|
Lecture 54 - Decision Problems of Regular Languages
|
|
|
|
Notes 52,53,54 - Lecture 52,53,54 - Decision Problems of Regular Languages Annotated Notes
(275 pages)
|
|
|
|
Lecture 55 - Practice of Regular Languages Decision Problems
|
|
|
|
Lecture 56 - Revision & Practice of CFGs
|
|
|
|
Notes 55,56 - Lecture 55,56 - Revision & Practice of CFGs Annotated Potes
(176 pages)
|
|
|
|
Lecture 57 - Inherently Ambiguous CFLs, Simplification of CFGs
|
|
|
|
Notes 57 - Lecture 57 - Inherently Ambiguous CFLs, Simplification of CFGs Annotated Notes
(143 pages)
|
|
|
|
Lecture 58 - Simplification of CFGs
|
|
|
|
Lecture 59 - Normal Forms of CFGs
|
|
|
|
Notes 58,59 - Lecture 58,59 - Simplification of CFG, Normal Forms Annotated Notes
(234 pages)
|
|
|
|
Lecture 60 - Decision Problems of CFLs
|
|
|
|
Lecture 61 - Universal TM, Acceptance Problem of TMs
|
|
|
|
Lecture 62 - Halting Problem of TM, Existence of Non-RE Language
|
|
|
|
NNotes 60,61,62 - Lecture 60,61,62 - Decision Problesm of CFLs, Undecidability, Halting Problems Annotated Notes
(208 pages)
|
|
|
|
Lecture 63 - Rice Theorem
|
|
|
|
Notes 63 - Lecture 63 - Rice Theorem Annotated Notes
(114 pages)
|
|
|
|
Lecture 64 - Rice Theorem Questions
|
|
|
|
Lecture 65 - Rice Theorem for Programs
|
|
|
|
Notes 64,65 - Lecture 64,65 - Rice Theorem for Programs Annotated Notes
(181 pages)
|
|
|
|
Lecture 66 - GATE Questions on Decidability
111:00
|
|
|
|
Notes 66 - Lecture 66 - GATE Questions on Decidability Annotated Notes
(61 pages)
|
|
|
|
Lecture 67 - Reductions
|
|
|
|
Lecture 68 - Reductions and Decision Problems of RE languages
|
|
|
|
Notes 67,68 - Lecture 67,68 - Reductions and Decision Problems of RE languages Annotated Notes
(209 pages)
|
|
|
|
Lecture 69 - Closure Properties of RE, REC Languages
180:00
|
|
|
|
Notes 69 - Lecture 69 - Closure Properties of RE,REC Languages, Complement Theorem Annotated Notes
(187 pages)
|
|
|
Module 4 - Countability
|
|
|
|
Mod 4 - Lecture 1 - Countability
98:00
|
|
|
|
Mod 4 - Lecture 2 - Countability Part 2
89:00
|
|
|
|
Mod 4 - Lecture 3 - Uncountable Sets and Cantor Theorem
120:00
|
|
|
|
Notes - Mod 4 - Lecture 1,2,3 - Countability Annotated Notes
(220 pages)
|
|
|
Homeworks
|
|
|
|
Homework 1 - Basic Concepts - Peter Linz Exercise 1.2 Questions
(27 pages)
|
|
|
|
Homework 2 - Basics, DFA - Boston University Questions
(38 pages)
|
|
|
|
Homework 3 - DFA Construction - IITB Questions
(26 pages)
|
|
|
|
Homework 4 - Set Theoretic Properties of Languages
(32 pages)
|
|
|
|
Homework 5 - More Questions on Basic Concepts
(33 pages)
|
|
|
|
Homework 6 - Some More Questions on Basic Questions
(24 pages)
|
|
|
|
Homework 7 - Finite Automata GATE Questions
(50 pages)
|
|
|
|
HW 7 Solutions
|
|