E0 222 Automata Theory and Computability
Instructor:
Deepak
D'Souza.
Teaching Assistants: Sumesh Divakaran
(sumeshdivakaran@gmail.com), M. A. Raghunandan (raghunandan.ma@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

03082011: Overview.

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

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

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

17082011: Homomorphisms. Slides.
 26082011: Synchronising
DFA's (Lecture by
Raghunandan).

29082011: Pumping lemma, ultimate periodicity.
Slides.
 02092011: Quiz +
(3 lectures)
MyhillNerode theorem: MN relations, MN rels for L = DFAs
for L,
Canonical MN relation for L, Algo to compute it.
Slides.
 12092011:
(2 lectures)
Buchi's Logical Characterisation of Regular Langs.
Proof. Slides.
 19092011: Intro to ContextFree Grammars. Slides.
 23092011: Chomsky Normal Form. Slides.
 26092011: Midsem test.
 30092011: Discussion on Midsem test.
 03102011: Pumping Lemma for CFL's. Slides.
 07102011: Parikh's Theorem. Slides.
 10102011: Intro to PDA's. Slides.
 14102011: Equivalence with CFL's. Slides.
 17102011: Reachability in pushdown systems.
 21102011: (2 lectures) Complementing DPDA's. Slides.
Slides.

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

11112011: Special lecture by Suman Bandyopadhay.
Slides.

18112011: Equivalent Models of Turing Machines.
Slides.

21112011: Halting Problem.
Slides.

24112011 (3:30pm): More undecidable problems.
Slides.

25112011: Reductions and Rice's Theorems.
Slides.

28112011: Undecidable problems about CFLs.
Slides.

30112011 (10:00am): 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
 Arden's Theorem, and Kleene Algebra. Nikhil and Harikrishna, 5pm,
Mon 17th Oct.
 Cellular Automata. Ankit and Shuvam, 5pm Thu 20th Oct.
 Regularity
preserving relations. See also
writeup
by Kozen. Aastha and Dilpreet, 5pm Mon 24th Oct.
 Deciding Presburger Arithmetic using automata.
Paper by
Hubert Comon. Raveendra Kumar, 5pm Thu 27th Oct.
Slides.
 Twoway DFA's. Srujana Oruganti and Srujana S, 5pm Fri 4rd Nov.
 A linear
algorithm for testing equivalence of finite automata,
J.E. Hopcroft and R.M.Karp (1971). D. Santosh Kumar,
P. Kiran Prasad, 5pm Fri 11 Nov.
 CKY parsing algorithm
and CFL
reachability. Pallavi Maiya and P K Lagena. 5pm Tue 15th Nov.
 Collapsing Nondeterministic automata.
Remish Leonard Minz and Tarun Jangpangi. 5pm Fri 18th Nov.
Slides.
 Cook's theorem (NPcompleteness of SAT). Vishwa and Narayan. 5pm Mon 21st Nov.
 The ChomskySchutzenberger theorem. Deepali Nemade and Nikhil Kumar.
5pm Thu 24th Nov.
Slides.
 Interface Automata. Tejas Patil and Amol Kamble. 5pm Fri 25th Nov.
 Murecursive functions capture Turing computable functions.
Prashant and Rahul.
5pm Mon 28th Nov.
 Undecidability of Post Correspondence Problem and Tiling
Problem.
Guarav Choudhary and Sunil Kumar. 5pm Wed 30 Nov.
 Context Sensitive Grammars and Linear Bounded Automata.
Aparna Vijayan and Indu John.
Slides (CSL)
Slides (LBS).
 Cellular Automata and nonlinear functions..
Sambaran and Jay Nandi.
 Derivatives of Regular expressions
(paper
by Brzozowski). See also
Regular expressions to DFA's (paper by Berry and
Sethi). Anita Chandel and Srimanta.

Weightage for evaluation:

Midsemester Exam: 20%

Assignments (Lab + written) + Seminar: 40%

Final Exam: 40%

Current meeting schedule: Mon 10:00 am, Fri 11:30am in CSA Lecture Room
(Room 117).
 Exam Schedule:

Midsemester Exam:
9:30am on Mon 26th September 2011.

Final Exam:
10:00am Wed 7th December 2011.