E0 222 Automata Theory and Computability
Instructors:
Deepak D'Souza and
Priti Shankar.

Course outline
 Finitestate automata, including the MyhillNerode theorem, ultimate
periodicity, and Buchi's logical characterization.
 Pushdown automata and Contextfree languages, including
deterministic PDA's, Parikh's theorem, and the
ChomskyShutzenberger theorem.
 Turing machines and undecidability, including Rice's theorem and Godel's
incompleteness theorem.
 Books and other material

Dexter Kozen: Automata and Computability. Springer 1999.

Hopcroft J.E. and Ullman J.D.: Introduction to Automata, Languages
and Computation. Addison Wesley, 1979.

Wolfgang Thomas: Automata on infinite objects, in Handbook of
Theoretical Computer Science, Volume B, Elsevier, 1990.
 H. R. Lewis and C. H. Papadimitriou: Elements of the
Theory of Computation. Prentice Hall, 1981.
 Note on Buchi's MSO characterisation of regular
languages.
 A linear
algorithm for testing equivalence of finite automata,
J.E. Hopcroft and R.M.Karp (1971).
 Assignments
 Seminar Topics

Weightage for evaluation:

Midsemester Exam: 20%

Assignments (Lab + written) + Seminar: 40%

Final Exam: 40%

Current meeting schedule: Tue & Thu 11:30 am, in EClassroom.
 Exam Schedule:

Midsemester Exam: TBA.

Final Exam: 10:00am Tue 11th December 2008.