
COL352: Introduction to Automata and Theory of Computation

Announcements 

Instructor 
Naveen Garg, 515 Bharti 
Text 
Introduction to Automata Theory. Languages and Computation;
Hopcroft,
Motwani and Ullmann; Pearson Education 
Reference
Material 
 Elements of the Theory of Computation; Lewis and
Papadimitriou;
Pearson
Education
 Automata and Computability; Kozen

Course
outline (tentative) 
Topic 
Slides

Tentative Dates

Introduction

intro

4

Regular expressions

1, 2, 3

8

Finite Automata  deterministic and nondeterministic

1, 2, 3 
11, 13

Regular languages, properties, pumping lemma


15, 18

Contextfree 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 

PSpace completeness

1 


Tutorial Sheets

Date given

Tutorial Sheet

Solutions

Jan 12

tut1















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.
