COL352: Introduction to Automata and Theory of Computation

Instructor Naveen Garg, 515 Bharti
Text Introduction to Automata Theory. Languages and Computation; Hopcroft, Motwani and Ullmann; Pearson Education
Reference Material
  1. Elements of the Theory of Computation; Lewis and Papadimitriou; Pearson Education
  2. Automata and Computability; Kozen
Course outline (tentative)
Topic Slides
Tentative Dates
Regular expressions 1, 2, 3 8
Finite Automata - deterministic and non-deterministic 1, 2, 3 11, 13
Regular languages, properties, pumping lemma

15, 18
Context-free languages
1, 2, 3
Pushdown Automata
1, 2
Properties of CFLs
1, 2
Turing Machines
1, 2
Decidability and Undecidability
1, 2
P, NP, Polytime reductions
1, 2, 3
P-Space completeness
Tutorial Sheets

Date given
Tutorial Sheet
Jan 12

Evaluation Minor1 (20); Minor2 (25); Major (40); 4 surprise lecture quizzes, best 3 to be counted, weightage of 5 marks each
Attendance/missed tests Policy
If you miss a minor due to illness (medical certificate needed) then I will scale the marks you receive  in the other minors and major to award you marks in the missed minor. There is no reminor. If you miss a lecture quiz there is no possibility of compensating it.