E0 222 Automata Theory and Computability
Vasantha Laxmi and Hari Shankar Gupta.
- 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, Reachability in Pushdown systems, 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
Wolfgang Thomas: Notes on applied automata theory
- Seminar Topics
- Derivatives of Regular expressions
by Brzozowski). See also
Regular expressions to DFA's (paper by Berry and
Sethi). (Srikanth and Jagadesh)
- Two-way DFA's. (Samrat and Chandrakanth)
preserving relations. See also
by Kozen. (Saumitra and Nikhil)
- Pattern Matching (Pavan Kumar and Harish Kumar Ande)
- Arden's Theorem (Rakesh Kumar Mallick and Anshul Gangwar).
- Deciding Presburger Arithmetic using automata. Reference: Sipser's book. (Shubha Jain) Slides.
- A linear
algorithm for testing equivalence of finite automata,
J.E. Hopcroft and R.M.Karp (1971). (Chintan Rao, Vijeth: 11:30am Mon 23 Nov). Slides.
- Collapsing Non-deterministic automata. (Rajesh S. and Rajendu Mitta: 12:15pm Mon 23 Nov)
- Interface Automata (Ashwin Prasad, Pranav: 3:30pm Wed 25th Nov). Slides.
- Context Sensitive Grammars and Linear Bounded Automata. (Premm Raj and Anirudh Santhiar: 4:15pm Wed 25th Nov)
- CKY parsing algorithm. (Kushal Wadhwani and Puneet Kumar Birwa: 11:30am Mon 30 Nov)
- The Chomsky-Schutzenberger theorem. (Ramakrishna and Kiran: 12:15pm Mon 30 Nov).
- Regular approximation of CFGs (Hiranya, Prithayan Barua)
- Undecidability of Post Correspondence Problem and Tiling Problem. (Karmaveer + Jitin)
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: 11:30am Thu 8th October 2009.
Final Exam: 2:00pm Sun 6th December 2009.