E0 222 Automata Theory and Computability

Teaching Assistants: Sumesh Divakaran (sumeshdivakaran@gmail.com), M. A. Raghunandan (raghunandan.ma@gmail.com).

• Course outline
  • 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 Chomsky-Shutzenberger theorem.
  • Turing machines and undecidability, including Rice's theorem and Godel's incompleteness theorem.

• Lectures
  1. 03-08-2011: Overview.
  2. 05-08-2011: DFA: intro, examples, definitions. Slides.
  3. 08-08-2011: Closure properties: induction, product construction, correctness, non-determinism, subset construction. Slides.
  4. 11-08-2011: Regular expressions: RE=DFA, Kleene, equation solving. Slides.
  5. 17-08-2011: Homomorphisms. Slides.
  6. 26-08-2011: Synchronising DFA's (Lecture by Raghunandan).
  7. 29-08-2011: Pumping lemma, ultimate periodicity. Slides.
  8. 02-09-2011: Quiz + (3 lectures) Myhill-Nerode theorem: MN relations, MN rels for L = DFAs for L, Canonical MN relation for L, Algo to compute it. Slides.
  9. 12-09-2011: (2 lectures) Buchi's Logical Characterisation of Regular Langs. Proof. Slides.
  10. 19-09-2011: Intro to Context-Free Grammars. Slides.
  11. 23-09-2011: Chomsky Normal Form. Slides.
  12. 26-09-2011: Midsem test.
  13. 30-09-2011: Discussion on Midsem test.
  14. 03-10-2011: Pumping Lemma for CFL's. Slides.
  15. 07-10-2011: Parikh's Theorem. Slides.
  16. 10-10-2011: Intro to PDA's. Slides.
  17. 14-10-2011: Equivalence with CFL's. Slides.
  18. 17-10-2011: Reachability in pushdown systems.
  19. 21-10-2011: (2 lectures) Complementing DPDA's. Slides. Slides.
  20. 04-11-2011: Turing Machines: intro, recursive and re lang defns. Slides.
  21. 11-11-2011: Special lecture by Suman Bandyopadhay. Slides.
  22. 18-11-2011: Equivalent Models of Turing Machines. Slides.
  23. 21-11-2011: Halting Problem. Slides.
  24. 24-11-2011 (3:30pm): More undecidable problems. Slides.
  25. 25-11-2011: Reductions and Rice's Theorems. Slides.
  26. 28-11-2011: Undecidable problems about CFLs. Slides.
  27. 30-11-2011 (10:00am): Godel's Incompletness Thm. Slides.

• Books and other material
  1. Dexter Kozen: Automata and Computability. Springer 1999.
  2. Hopcroft J.E. and Ullman J.D.: Introduction to Automata, Languages and Computation. Addison Wesley, 1979.
  3. Wolfgang Thomas: Automata on infinite objects, in Handbook of Theoretical Computer Science, Volume B, Elsevier, 1990.
  4. H. R. Lewis and C. H. Papadimitriou: Elements of the Theory of Computation. Prentice Hall, 1981.
  5. Note on Buchi's MSO characterisation of regular languages.
  6. Wolfgang Thomas: Notes on applied automata theory

• Assignments
  • Assignment 1 due on Fri 26 August 2011.
  • Assignment 2 due on Fri 23 September 2011.
  • Assignment 3 due on Fri 28th October 2011.
  • Assignment 4 due on Fri 25 November 2011.
  • Assignment 5 due on Tue 06 December 2011.

• Seminar Topics
  • Arden's Theorem, and Kleene Algebra. Nikhil and Harikrishna, 5pm, Mon 17th Oct.
  • Cellular Automata. Ankit and Shuvam, 5pm Thu 20th Oct.
  • Regularity preserving relations. See also writeup by Kozen. Aastha and Dilpreet, 5pm Mon 24th Oct.
  • Deciding Presburger Arithmetic using automata. Paper by Hubert Comon. Raveendra Kumar, 5pm Thu 27th Oct. Slides.
  • Two-way DFA's. Srujana Oruganti and Srujana S, 5pm Fri 4rd Nov.
  • A linear algorithm for testing equivalence of finite automata, J.E. Hopcroft and R.M.Karp (1971). D. Santosh Kumar, P. Kiran Prasad, 5pm Fri 11 Nov.
  • CKY parsing algorithm and CFL reachability. Pallavi Maiya and P K Lagena. 5pm Tue 15th Nov.
  • Collapsing Non-deterministic automata. Remish Leonard Minz and Tarun Jangpangi. 5pm Fri 18th Nov. Slides.
  • Cook's theorem (NP-completeness of SAT). Vishwa and Narayan. 5pm Mon 21st Nov.
  • The Chomsky-Schutzenberger theorem. Deepali Nemade and Nikhil Kumar. 5pm Thu 24th Nov. Slides.
  • Interface Automata. Tejas Patil and Amol Kamble. 5pm Fri 25th Nov.
  • Mu-recursive functions capture Turing computable functions. Prashant and Rahul. 5pm Mon 28th Nov.
  • Undecidability of Post Correspondence Problem and Tiling Problem. Guarav Choudhary and Sunil Kumar. 5pm Wed 30 Nov.
  • Context Sensitive Grammars and Linear Bounded Automata. Aparna Vijayan and Indu John. Slides (CSL) Slides (LBS).
  • Cellular Automata and non-linear functions.. Sambaran and Jay Nandi.
  • Derivatives of Regular expressions (paper by Brzozowski). See also Regular expressions to DFA's (paper by Berry and Sethi). Anita Chandel and Srimanta.

• Weightage for evaluation:
  • Mid-semester Exam: 20%
  • Assignments (Lab + written) + Seminar: 40%
  • Final Exam: 40%

• Current meeting schedule: Mon 10:00 am, Fri 11:30am in CSA Lecture Room (Room 117).

• Exam Schedule:
  • Mid-semester Exam: 9:30am on Mon 26th September 2011.
  • Final Exam: 10:00am Wed 7th December 2011.