
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 NonDeterministic 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  NonRegular Languages
135:00




Notes 26  Lecture 26  Nonregular languages Annotated Notes
(142 pages)




Lecture 27  Distinguishable Strings, NonRegular Languages
116:00




Lecture 28  Myhill Nerode Theorem & NonRegular Languages
51:00




Notes 27,28  Lecture 27,28  Myhill Nerode Theorem & NonRegular 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 NonDeterminism
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 & ChurchTuring Thesis




Notes 44, 45  Lecture 44,45  Computability & ChurchTuring 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 NonRE 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

