E0 222 Automata Theory and Computability
Instructors:
Deepak D'Souza and
Priti Shankar.
Teaching Assistants: Deepak R
(deepakr@csa.iisc.ernet.in), Pranavadatta (pranavad@csa.iisc.ernet.in), and Chintan Rao(chintanraoh@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

05082010: Overview.
 No class on Thu 07082010 due to Perspective Seminars.

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

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

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

24082010: Quiz + Homomorphisms. Slides.

26082010: Pumping lemma, ultimate periodicity.
Slides.

(3 lectures)
MyhillNerode theorem: MN relations, MN rels for L = DFAs
for L,
Canonical MN relation for L, Algo to compute it.
Slides1, Slides2.

(2 lectures)
Buchi's Logical Characterisation of Regular Langs.
Proof. Slides.
 21092010: Midsem test.
 23092010: discussion on Midsem test.
 28092010: Intro to ContextFree Grammars. Slides.
 30092010: Chomsky Normal Form. Slides.
 05102010: Pumping Lemma for CFL's. Slides.
 0710.2010: Intro to PDA's. Slides.
 12102010: Equivalence of acceptance by Final State and Empty Stack.
Slides.
 14102010: Equivalence with CFL's. Slides.
 26102010: Complementing DPDA's. Slides.
 28102010: Reachability in Pushdown systems.
Slides.
 02112010: Parikh's Theorem.
Slides.

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

11112010: Equivalent Models of Turing Machines.
Slides.

12112010: Halting Problem.
Slides.

16112010: More undecidable problems.
Slides.

18112010: Reductions and Rice's Theorems.
Slides.

23112010: Undecidable problems about CFLs.
Slides.

25112010: Godel's Incompletness Thm.
Slides.

30112010, 3:30pm: Special lecture by Suman Bandyopadhay.
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
 Seminar Topics
 Deciding Presburger Arithmetic using automata. paper by Comon. Arvind and Mallesham 17 September.
Slides.
 Arden's Theorem, and Kleene Algebra. Vinod Jadhao and Sravan, 1st October.
 Regularity
preserving relations. See also
writeup
by Kozen. Madhav and Adinarayana, 14 October, 5:00pm.
Slides.
 A linear
algorithm for testing equivalence of finite automata,
J.E. Hopcroft and R.M.Karp (1971). Bhavana and Gurpreet. 15 October, 5:30pm. Slides.
 Regular approximation of
CFGs, Harikrishna and Shalini, 22 October. Slides.
 Collapsing Nondeterministic automata. Punya Murthy and Prabhakaran. 29 October.
 Twoway DFA's. Girish Maskeri Rama. 11 November.
Slides.
 Interface Automata. Jay Thakkar and Amogh Margoor. 12 November.
Slides.
 CKY parsing algorithm and CFL reachability. Ravindra and Suresh. 18 November.
 Context Sensitive Grammars and Linear Bounded Automata. Arvind S R and Omesh Pandita Seminar. 19 November.
 Undecidability of Post Correspondence Problem and Tiling
Problem. Raghunandan. 25 November.
 Murecursive functions capture Turing computable functions.
26 November.
 Derivatives of Regular expressions
(paper
by Brzozowski). See also
Regular expressions to DFA's (paper by Berry and
Sethi). Parag Jambhulkar. 5:00pm 6th December.
Slides.
 The ChomskySchutzenberger theorem.

Weightage for evaluation:

Midsemester Exam: 20%

Assignments (Lab + written) + Seminar: 40%

Final Exam: 40%

Current meeting schedule: Tue & Thu 11:30 am, in CSA Lecture Room.
 Exam Schedule:

Midsemester Exam: 11:30am on Tue 21st September 2010.

Final Exam: 10:00am Thu 9th December 2010..