In Semester 2, 2018-2019, I will be teaching CS 2200: Languages, Machines and Computation.

### Administrative Information.

#### When and Where.

Classes are held on Monday 9 am, Tuesday 8 am, Wednesday 1 pm and Friday 11:00 am. Location: CSB 36.

#### Office Hours and Teaching Assistants.

The teaching assistants for the course are listed below. Office hours to be decided.

- Rachit Garg. Email: CS14B050@smail.iitm.ac.in
- Monosij Maitra. Email: CS15D010@smail.iitm.ac.in
- Ankit Kumar Yadav. Email: CS16S039@smail.iitm.ac.in
- Shiladitya Biswas. Email: CS17M043@smail.iitm.ac.in
- Rajarshi Biswas. Email: CS17S007@smail.iitm.ac.in
- Anshu Yadav. Email: CS18D008@smail.iitm.ac.in
- Vankam Sree Hari. Email: CS17M059@smail.iitm.ac.in
- Nisha K K. Email: CS18D002@smail.iitm.ac.in
- Anoop S K M. Email: CS18D003@smail.iitm.ac.in
**Tutorials:**29/01/19, 06/02/19, 08/02/19, 13/02/19, 22/02/19, 06/03/19, 18/03/19, 20/03/19, 03/04/19, 10/04/19, 23/04/19.**Short Exams:**08/02/19, 06/03/19, 20/03/19, 23/04/19.**Minor and Major exams:**19/02/19, 26/03/19 and 30/04/19.- Rachit: Thursday 3:30-4:30 pm.
- Monosij: Friday, 4.30 -5.30 pm.
- Ankit: Friday, 4.00 -5.00 pm.
- Shiladitya: Wednesday 4:00 -5:00 pm.
- Sree Hari: Thursday 5:00 -6:00 pm.
- Rajarshi: Friday 4:30 - 5:30 pm.
- Nisha: Thursday 4:00 - 5:00 pm.
- Anoop: Thursday 4:00 -5:00 pm.
- Anshu: Wednesday 3:00 -4:00 pm.
**Finite Automata & Regular Languages (Ch 1 of Sipser, Ch 13-16 of Kozen):**Introduction to automata theory, languages and computational problems. Finite state automata, Regular Languages. Deterministic and Non-deterministic finite automata, Subset construction. Regular Expressions, Pattern Matching, pumping lemma, DFA state minimization, Myhill Nerode relations, Myhill Nerode theorem.**Context Free Languages and Push Down Automata (Ch 2 of Sipser and Ch 20 and 27 of Kozen) :**Context free grammars - Derivation trees and ambiguity -Chomsky normal form - Pushdown automata - Acceptance by empty store and final state - Equivalence between push-down automata and context-free grammars - Pumping lemma - PAREN language and its grammar - CYK algorithm - Closure properties of CFL.

**Turing machines & Computability (Ch 3, 4 and 5 of Sipser):**Techniques for Turing machine construction - Generalized and restricted versions equivalent to the basic model - Universal Turing machine - Turing recognizable and decidable - linear bounded automata. Decidability; Post's correspondence problem; Rice's theorem; decidability of membership, emptiness and equivalence problems of languages, reductions.

- 2 Quizzes: 20% each.
- Final Exam: 40%.
- Tutorials: 20% distributed over 4 short exams 5% each.

TA Office hours: