E0 222 Automata Theory and Computability
Instructor:
Deepak
D'Souza.
Teaching Assistants: Sabuj Kumar Jena (sabuj.jena@csa.iisc.ernet.in), Hari Krishna Malladi (harikrishnamalladi.iisc@gmail.com), Parixit Prasad (parixit.prasad@csa.iisc.ernet.in), Sachin Srivastava (sachin.srivastava@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

06082014: Course overview.

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

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

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

20082014: Homomorphisms. Slides.

27082014: Pumping lemma, ultimate periodicity.
Slides.
 01092014:
(2 lectures)
MyhillNerode theorem: MN relations, MN rels for L = DFAs
for L,
Canonical MN relation for L, Algo to compute it.
Slides.
 08092014: (2 lectures)
Buchi's Logical Characterisation of Regular Langs.
Proof. Slides.
 15092014: Intro to ContextFree Grammars. Slides.
 17092014: Chomsky Normal Form. Slides.
 22092014: Pumping Lemma for CFL's. Slides.
 29092014: Parikh's Theorem. Slides.
 01102014: Midsem test.
 13102014: Discussion on Midsem test.
 15102014: Intro to PDA's. Slides.
 20102014: Equivalence with CFL's. Slides.
 22102014: Reachability in pushdown systems.
Slides.
 27102014: Complementing DPDA's. Slides.

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

04112014: Equivalent Models of Turing Machines.
Slides.

10112014: Quiz on Turing Machines.

12112014: Halting Problem.
Slides.

17112014: More undecidable problems.
Slides.

19112014: Reductions and Rice's Theorems.
Slides.

24112014: Undecidable problems about CFLs.
Slides.

26112014: 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
 Deciding Presburger Arithmetic using automata.
Paper by
Hubert Comon (Section 8). Athmanathan and Terrance, 11:00am, Fri 31 October. Slides.
 Buchi Automata and their closure properties. Ajith S. and Ankit Kumar Fri 7th Nov 10:00am
Slides.
 Direct automaton construction for Parikh's Theorem.
Paper by Esparza, Ganty, Kiefer, Luttenberger. Marilyn and Cressida. 7th Nov 11am.
Slides.
 Cook's theorem (NPcompleteness of SAT). Sandip Sinha and Anamay. 11:00am Fri 14th Nov.
Slides.
 Undecidability of validity problem of FirstOrder Logic.
(see Rob van Glabbeek's notes).
Sabareesh and Milind. 11:00am Fri, 21st Nov.
 Regularity
preserving relations. See also
writeup
by Kozen. Ankit Jaiswal and Rekha. Sat 22nd Nov, 9:00am.
Slides.
 CKY parsing algorithm
and CFL
reachability.
 The ChomskySchutzenberger theorem. Rohit and Varun, 12:00pm Tue 25th Nov.
 Twoway DFA's. Sajith, Thu 27th Nov, 12:00pm.
 Angluin's algorithm for learning regular languages. Ramana Venkata, Fri 28th Nov, 11:00am
 Collapsing Nondeterministic automata. Mukund Seethamraju, Tue 02 Dec, 12:00pm.
Slides.
 Arden's Theorem, and Kleene Algebra.
 Visibly Pushdown Languages.
 A linear
algorithm for testing equivalence of finite automata,
J.E. Hopcroft and R.M.Karp (1971).
 Context Sensitive Grammars and Linear Bounded Automata.
 Nested word automata. Paper by Alur and Madhusudan.
 Algebraic view of Automata.
 Undecidability of Post Correspondence Problem and Tiling
Problem.
 Murecursive functions capture Turing computable functions.

Weightage for evaluation:

Midsemester Exam: 20%

Assignments (Lab + written) + Seminar: 40%

Final Exam: 40%

Current meeting schedule: Mon, Wed, 9:30 am, CSA Lecture Hall
(Room 117).
 Exam Schedule:

Midsemester Exam:
9:00am Wed 1st Oct 2014.

Final Exam:
9:00am Thu 04 Dec 2014.