Theory of Computation

(Autumn 2013)


Instructor :  B Srivathsan
 
TAs : Chandra Sekhar       Gautam Gopal       Abhishek Oswal


Hours

Lectures Mon 10:30 - 11:45 Lecture Hall 6
Fri   2:00 - 3:15 Lecture Hall 6
 
Tutorials Thu   6:00 PM onwards

Grading

Quizzes 20%
Mid-semester exam 30%
End-semester exam 50%

References

[1]   D. Kozen: Automata and Computability, Springer.

[2]   J. E. Hopcroft and J. D. Ullman: Introduction to Automata, Languages and Computation, Narosa (Third edition).

[3]   Sipser: Introduction to the Theory of Computation, PWS Publishing Company

Tutorial Sheets

Tutorial 1       Tutorial 2       Tutorial 3       Tutorial 4       Tutorial 5

Tutorial 6       Tutorial 7       Tutorial 8       Tutorial 9


Lectures



Class 0 05.08.2013 (Mon) Motivation to the course   Slides
Class 1 12.08.2013 (Mon) Lectures 2, 3, 4 of [1]
Class 2 16.08.2013 (Fri) Lectures 5, 6 of [1]
Class 3 19.08.2013 (Mon) Sections 2.5.1 - 2.5.5 of [2]
Class 4 23.08.2013 (Fri) Section 2.3 of [3]
Class 5 26.08.2013 (Mon) Lecture 10 of [1]
Section 2.4 of [3]
Class 6 30.08.2013 (Fri) Lecture 13, 14 of [1]
Class 7 02.09.2013 (Mon) Lecture 15, 16 of [1]
Class 8 13.09.2013 (Fri) Lecture 19, 20 of [1] and Linz (Notation: this text uses the word variable for non-terminal)
Class 9 18.09.2013 (Wed) Linz
Class 10 04.10.2013 (Fri) Section 2.1 of [3] (Chomsky Normal Form)
Class 11 07.10.2013 (Mon) Lecture 23, Supplementary lecture E of [1]
Class 12 11.10.2013 (Fri) Lecture 24, 25 of [1]
Class 13 18.10.2013 (Fri) Lecture 28, 29 of [1]
Class 14 20.10.2013 (Mon) Lecture 30 of [1] (up to two-stack automata)
Class 15 25.10.2013 (Fri) Rest of Lecture 30 of [1], Non-deterministic T.M.s from Sipser
Class 16 28.10.2013 (Mon) Lecture 31 of [1]
Class 17 6.11.2013 (Wed) Lecture 32, 33 of [1]
Class 18 8.11.2013 (Fri) Lecture 34 of [1]
Class 20 11.11.2013 (Mon) Sections 5.1 and 5.2 from [3]
Class 21 15.11.2013 (Fri) Overview of Lectures 36, 38, 39 of [1]