E0 222 Automata Theory and Computability (formerly FMCS)

• Course outline

  The course will essentially be a course on Theory of Computation.

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

• 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. A linear algorithm for testing equivalence of finite automata, J.E. Hopcroft and R.M.Karp (1971).

• Assignments
  • Assignment 1 due on Thu 23 August 2007.
  • Assignment 2 due on Tue 18 September 2007.
  • Assignment 3 due on Fri 2 November 2007.
  • Assignment 4 due on Fri 30 November 2007.
  • Practice questions on PCP.

• Seminar Topics
  • Derivatives of Regular expressions (paper by Brzozowski): Ravi Shanker Yadav & Baiger Sahebrao Sidram, Mon 27th Aug, 11:30am.
  • Regular expressions to DFA's (paper by Berry and Sethi).
  • Kleene Algebras and Regular Expressions
  • Two-way DFA's (Jimmy Bahuleyan, Sumesh Divakaran: 10 Sept.)
  • Ogden's Lemma (Vasantha Lakshmi: 29 Oct).
  • Magic Numbers and Subset Construction
  • Regularity preserving relations. See also writeup by Kozen.
  • CKY parsing algorithm (Hari Prasad and Kalyan: 26th Nov)
  • Context Sensitive Grammars and Linear Bounded Automata
  • Collapsing Non-deterministic automata
  • The Chomsky-Schutzenberger theorem (Harsh Srirmal and Vasu Babu: 30th Nov)
  • Regular approximation of CFGs
  • Grammars as Processes (paper by Esparza).
  • Mu-recursive functions capture Turing computable functions (Abhijeet Pai: 29th Nov).
  • Undecidability of Post Correspondence Problem and Tiling Problem.
  • Grammars and computability.
  • Term automata.

• 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:00am on Tue 9th October 2007.
  • Final Exam: 10:00am Tue 11th December 2007.