E0 222 Automata Theory and Computability
Deepak D'Souza and
- Finite-state automata, including the Myhill-Nerode theorem, ultimate
periodicity, and Buchi's logical characterization.
- Pushdown automata and Context-free languages, including
deterministic PDA's, Parikh's theorem, and the
- Turing machines and undecidability, including Rice's theorem and Godel's
- 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
- A linear
algorithm for testing equivalence of finite automata,
J.E. Hopcroft and R.M.Karp (1971).
- Seminar Topics
Weightage for evaluation:
Mid-semester Exam: 20%
Assignments (Lab + written) + Seminar: 40%
Final Exam: 40%
Current meeting schedule: Tue & Thu 11:30 am, in E-Classroom.
- Exam Schedule:
Mid-semester Exam: TBA.
Final Exam: 10:00am Tue 11th December 2008.