E0 222 Automata Theory and Computability
Instructor:
Deepak
D'Souza.
Teaching Assistants: Sumesh Divakaran
(sumeshdivakaran@gmail.com), Suvam Mukherjee(suvam@csa.iisc.ernet.in).

Course outline
 Finitestate automata, including the MyhillNerode theorem, ultimate
periodicity, and Buchi's logical characterization.
 Pushdown automata and Contextfree languages, including
deterministic PDA's, Parikh's theorem, Reachability in Pushdown systems, and the
ChomskyShutzenberger theorem.
 Turing machines and undecidability, including Rice's theorem and Godel's
incompleteness theorem.

Lectures

07082012: Course overview.

09082012: DFA: intro, examples, definitions. Slides.

14082012: Closure properties: induction, product construction2
correctness, nondeterminism, subset construction. Slides.

16082012: Regular expressions: RE=DFA, Kleene, equation solving.
Slides.

21082012: Homomorphisms. Slides.

23082012: Pumping lemma, ultimate periodicity.
Slides.
 28082012: Lecture on Tree automata and program analysis by Helmut Seidl.
 30092012:
(3 lectures)
MyhillNerode theorem: MN relations, MN rels for L = DFAs
for L,
Canonical MN relation for L, Algo to compute it.
Slides.
 06092012: Quiz +
(2 lectures)
Buchi's Logical Characterisation of Regular Langs.
Proof. Slides.
 19092012: Intro to ContextFree Grammars. Slides.
 27092012: Midsem test.
 05102012: Discussion on Midsem test.
 09102012: Chomsky Normal Form. Slides.
 11102012: Pumping Lemma for CFL's. Slides.
 16102012: Parikh's Theorem. Slides.
 18102012: Intro to PDA's. Slides.
 19102012: Equivalence with CFL's. Slides.
 23102012: Reachability in pushdown systems.
Slides.
 25102012: Complementing DPDA's. Slides.

30102012: Turing Machines: intro, recursive and re lang defns.
Slides.

06112012: Equivalent Models of Turing Machines.
Slides.

08112012: Quiz on Turing Machines.

15112012: Halting Problem.
Slides.

20112012: More undecidable problems.
Slides.

22112012: Reductions and Rice's Theorems.
Slides.

27112012: Undecidable problems about CFLs.
Slides.

29112012: Godel's Incompletness Thm.
Slides.
 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
languages.

Wolfgang Thomas: Notes on applied automata theory
 Assignments
 Seminar Topics
 Twoway DFA's. (Tanuj Agarwal and Vishesh Garg, Fri 26th Oct 5:15pm).
Slides.
 Deciding Presburger Arithmetic using automata.
Paper by
Hubert Comon (Section 8). (Rashmi M, Wed 14th Nov, 5.15pm)
 A linear
algorithm for testing equivalence of finite automata,
J.E. Hopcroft and R.M.Karp (1971). (Yasar, Fri 16th Nov, 5.15pm).
 CKY parsing algorithm
and CFL
reachability. (Rajeev and Shibu, Fri 24th Nov, 5.15pm).
 Context Sensitive Grammars and Linear Bounded Automata. (Sumit Neelam Mon 26th Nov 2012).
 Regularity
preserving relations. See also
writeup
by Kozen. Himanshu Arora.
 Arden's Theorem, and Kleene Algebra.
 Collapsing Nondeterministic automata.
 Cook's theorem (NPcompleteness of SAT).
 The ChomskySchutzenberger theorem.
 Interface Automata.
 Murecursive functions capture Turing computable functions.
 Undecidability of Post Correspondence Problem and Tiling
Problem.
 Cellular Automata and nonlinear functions..
 Nested word automata. Paper by Alur and Madhusudan.
 Derivatives of Regular expressions
(paper
by Brzozowski). See also
Regular expressions to DFA's (paper by Berry and
Sethi).

Weightage for evaluation:

Midsemester Exam: 20%

Assignments (Lab + written) + Seminar: 40%

Final Exam: 40%

Current meeting schedule: Tue 2:00 pm, Thu 2:00am in CSA Lecture Hall
(Room 117).
 Exam Schedule:

Midsemester Exam:
1:30pm, 27 Sep 2012.

Final Exam:
10:00am, Sat 8th Dec 2012.