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

## Announcements

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

## Grading (tentative)

20% : Quizzes
20% : Each minor exam

40: Major exam