# COL 352 : Introduction to Automata and Theory of Computation

## Instructor

Amit Kumar
Office : Room # 417, Bharti Building
Email : amitk@cse.iitd.ac.in
Phone : (ext) 1286.

## Class Timings

Slot H, Monday, Wednesday 11-12 noon, Thursday 12-1pm.

## 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)

## Books

Elements of the Theory of Computation by Harry Lewis and Christos Papadimitriou.