COL 352 : Introduction to Automata and Theory of Computation

Instructor

Announcements

Class Timings

Lecture Topics

• Lecture 1: Introduction to the course
  
• Lecture 2: Regular Languages, Finite Automata (Sec. 1.7, 1.8)
  
• Lecture 3: Deterministic Automata, examples (Sec. 2.1)
  
• Lecture 4: Non-deterministic Finite Automata, examples (Sec 2.2)
  
• Lecture 5: Closure properties of NFA (Sec 2.3)
  
• Lecture 6: Equivalence of DFA and NFA (Sec 2.2)
  
• Lecture 7: Equivalence of DFA and regular expressions (Sec 2.3)
  
• Lecture 8: Pumping Lemma (Sec 2.4), Quiz I
  
• Lecture 9: Applications of Pumping Lemma (Sec 2.4)
  
• Lecture 10: Myhill Nerode Theorem and Applications(Sec 2.5)
  
• Lecture 11: DFA State Minimization (Sec 2.5)
  
• Letcure 12: Examples of DFA State Minimization (Sec 2.5), Quiz II
  
• Lecture 13: Context free grammars, parse trees. (Sec 3.1, 3.2)
  
• Lecture 14: Pushdown Automata, examples (Sec 3.3)
  
• Lecture 15: Closure properties, CFG can be recognized by PDA (Sec 3.4)
  
• Lecture 16: Every PDA can be described by a CFG (Sec 3.4)
  
• Lecture 17: Equivalence between PDA and CFG (Sec 3.4)
  
• Lecture 18: Pumping Lemma for PDA (Sec 3.5)
  
• Lecture 19: Applications of Pumping Lemma, more closure properties (Sec 3.5, 3.4)
  
• Lecture 20: Deterministic vs non-deterministic PDA (Sec 3.7)
  
• Lecture 21: CKY Algorithm (Sec 3.6)
  
• Lecture 22: Chmosky Normal Form, Quiz III (Sec 3.6)
  
• Lecture 23: Examples of Chomsky Normal Form, Ambiguous Grammars (Sec 3.6, Sec 3.2)
  
• Lecture 24: Introduction to Turing Machines, examples (Impartus Lecture 1, Sec 4.1, 4.2)
  
• Lecture 25: Recursive and recursively enumerable languages, TMs with multiple tapes (Impartus Lecture 2, Sec 4.2, 4.3)
  
• Lecture 26: Examples of Turing Machines with Multiple Tapes (Impartus Lecture 3, Sec 4.3)
  
• Lecture 27: Equivalence of TM with single tape and TM with multiple tapes (Impartus Lecture 4, Sec 4.3).
  
• Lecture 28: Robustness of TM with other extensions, Equivalence of TM and RAM model of computation (Impartus Lecture 5, Sec 4.3, 4.4)
  
• Lecture 29: Non-deterministic Turing Machines (Impartus Lecture 6, Sec 4.5)
  
• Lecture 30: Simulation of Non-deterministic TM by deterministic TM (Impartus Lecture 7, Sec 4.5)
  
• Lecture 31: Universal Turing Machines (Impartus Lecture 8, Sec 5.2)
  
• Lecture 32: Diagonalization, Halting Problem (Impartus Lecture 9, Sec 5.3)
• Lecture 33: Examples of Undecidable Problems (Impartus Lecture 10, Sec 5.4)
• Lecture 34: Rice's Thereom (Impartus Lecture 11, Sec 5.7)
• Lecture 35, 36: Undecidable Problems about CFG (Impartus Lecture 12,13, Sec 5.5)

Books

Grading (tentative)