E0 222 Automata Theory and Computability
Instructor:
Deepak
D'Souza.
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
 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

05082013: Course overview.

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

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

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

21082013: Homomorphisms. Slides.

23082013: Pumping lemma, ultimate periodicity.
Slides.
 28082013:
(3 lectures)
MyhillNerode theorem: MN relations, MN rels for L = DFAs
for L,
Canonical MN relation for L, Algo to compute it.
Slides.
 06092013: Quiz +
(2 lectures)
Buchi's Logical Characterisation of Regular Langs.
Proof. Slides.
 13092013: Intro to ContextFree Grammars. Slides.
 20092013: Chomsky Normal Form. Slides.
 23092013: Pumping Lemma for CFL's. Slides.
 27092013: Parikh's Theorem. Slides.
 30092013: Intro to PDA's. Slides.
 04102013: Midsem test.
 07102013: Discussion on Midsem test.
 19102013: Equivalence with CFL's. Slides.
 21102013: Reachability in pushdown systems.
Slides.
 25102013: Complementing DPDA's. Slides.

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

04112013: Equivalent Models of Turing Machines.
Slides.

11112013: Quiz on Turing Machines.

18112013: Halting Problem.
Slides.

22112013: More undecidable problems.
Slides.

25112013: Reductions and Rice's Theorems.
Slides.

27112013: Undecidable problems about CFLs.
Slides.

29112013: 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
 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.
 Twoway DFA's. Pavan Kumar Akulakrishna and Jagvir Singh. 3pm, Fri 29th Nov.
Slides1 and Slides2.
 The ChomskySchutzenberger 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 (NPcompleteness 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 Nondeterministic 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.
 Murecursive functions capture Turing computable functions. Arun Kumar and Chaitanya. Fri 6th Dec, 3:30pm.
Slides.
 Undecidability of validity problem of FirstOrder Logic.
(see Rob van Glabbeek's notes).

Weightage for evaluation:

Midsemester 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:

Midsemester Exam:
11:30am Fri 04 October 2013.

Final Exam:
9:30am Tue 10 Dec 2013.