E0 222 Automata Theory and Computability

Teaching Assistants: Himanshu Arora (himanshu.arora@csa.iisc.ernet.in), Rashmi Mudduluru (mudduluru.rashmi@csa.iisc.ernet.in), and Sumesh Divakaran (sumeshdivakaran@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. 05-08-2013: Course overview.
  2. 12-08-2013: DFA: intro, examples, definitions. Slides.
  3. 16-08-2013: Closure properties: induction, product construction2 correctness, non-determinism, subset construction. Slides.
  4. 19-08-2013: Regular expressions: RE=DFA, Kleene, equation solving. Slides.
  5. 21-08-2013: Homomorphisms. Slides.
  6. 23-08-2013: Pumping lemma, ultimate periodicity. Slides.
  7. 28-08-2013: (3 lectures) Myhill-Nerode theorem: MN relations, MN rels for L = DFAs for L, Canonical MN relation for L, Algo to compute it. Slides.
  8. 06-09-2013: Quiz + (2 lectures) Buchi's Logical Characterisation of Regular Langs. Proof. Slides.
  9. 13-09-2013: Intro to Context-Free Grammars. Slides.
  10. 20-09-2013: Chomsky Normal Form. Slides.
  11. 23-09-2013: Pumping Lemma for CFL's. Slides.
  12. 27-09-2013: Parikh's Theorem. Slides.
  13. 30-09-2013: Intro to PDA's. Slides.
  14. 04-10-2013: Midsem test.
  15. 07-10-2013: Discussion on Midsem test.
  16. 19-10-2013: Equivalence with CFL's. Slides.
  17. 21-10-2013: Reachability in pushdown systems. Slides.
  18. 25-10-2013: Complementing DPDA's. Slides.
  19. 28-10-2013: Turing Machines: intro, recursive and re lang defns. Slides.
  20. 04-11-2013: Equivalent Models of Turing Machines. Slides.
  21. 11-11-2013: Quiz on Turing Machines.
  22. 18-11-2013: Halting Problem. Slides.
  23. 22-11-2013: More undecidable problems. Slides.
  24. 25-11-2013: Reductions and Rice's Theorems. Slides.
  25. 27-11-2013: Undecidable problems about CFLs. Slides.
  26. 29-11-2013: 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 06 September 2013.
  • Assignment 2 due on Fri 20 September 2013.
  • Assignment 3 due on Fri 18th October 2013.
  • Assignment 4 due on Mon 4 November 2013.
  • Assignment 5 due on Fri 29 December 2013.

• Seminar Topics
  • Visibly Pushdown Languages, Sabuj Kumar Jena, Wed 23 Oct 2013. Slides.
  • A linear algorithm for testing equivalence of finite automata, J.E. Hopcroft and R.M.Karp (1971). Namrata Jain. 30 Oct. Slides.
  • CKY parsing algorithm and CFL reachability. Lohit Krishnan and Chetas Mahajan, 13th Nov. Slides.
  • Arden's Theorem, and Kleene Algebra. Anshul Kumar and Inzamamul Haq. 20th Nov. Slides.
  • Regularity preserving relations. See also writeup by Kozen. Priyanka Bhatt and Surabhi Punjabi. Thu 28th Nov, 5pm. Slides.
  • Context Sensitive Grammars and Linear Bounded Automata. Anup Sah and Hemanth. 5:15pm, 27th Nov. Slides.
  • Nested word automata. Paper by Alur and Madhusudan. Priyanka and Vibhuti, Thu 28th Nov. Slides.
  • Two-way DFA's. Pavan Kumar Akulakrishna and Jagvir Singh. 3pm, Fri 29th Nov. Slides-1 and Slides-2.
  • The Chomsky-Schutzenberger theorem. Pallavi Chugh and Ameet Gadekar. 5pm Monday 2nd Dec. Slides.
  • Buchi Automata and their closure properties. Aditya C and Raju V. 4pm Tue 3rd Dec.
  • Cook's theorem (NP-completeness of SAT). Sachin Srivastava and Suvita, 4 Dec, 5pm.
  • Deciding Presburger Arithmetic using automata. Paper by Hubert Comon (Section 8). Parixit Prasad. 6pm Wed 4th Dec. Slides.
  • Algebraic view of Automata. Snigdha Athaiya. 2pm, Thu 5th Dec.
  • Collapsing Non-deterministic automata. Abhishek and Aayush. 5pm, Thu 5th Dec. Slides.
  • Undecidability of Post Correspondence Problem and Tiling Problem. Akanksha Meghlan and Disha Makhija. 2:30pm Fri 6th Dec. Slides.
  • Mu-recursive functions capture Turing computable functions. Arun Kumar and Chaitanya. Fri 6th Dec, 3:30pm. Slides.
  • Undecidability of validity problem of First-Order Logic. (see Rob van Glabbeek's notes).

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

• Current meeting schedule: Mon 3:30 pm, Fri 11:30am in CSA Lecture Hall (Room 117).

• Exam Schedule:
  • Mid-semester Exam: 11:30am Fri 04 October 2013.
  • Final Exam: 9:30am Tue 10 Dec 2013.