Introduction to Automata Theory

Time:1:15 - 3:05pm, Tuesdays and Thursdays, Summer 2012.
Place:Skilling Auditorium
Instructor:Mridul Aanjaneya (aanjneya@stanford.edu)
Office hours:2:00PM - 4:00PM, Gates 206 (Mondays)
TA:Sean Kandel (skandel@cs.stanford.edu)
Office hours:6:00PM - 8:00PM, Gates 372 (Tuesdays and Thursdays)

Announcements

  • Discussion is now open on Lore with access code: R4ML4Z.
  • (07/03) Homework 1 is out. Due on (07/11).
  • (07/10) Homework 2 is out. Due on (07/18).
  • (07/17) Homework 3 is out. Due on (07/25).
  • (07/26) Homework 4 is out. Due on (08/09).

Schedule

Date Topic Notes
Tue, Jun 26 Introduction. Automata, Computability and Complexity.

[MS05] Chapters 0,1.

Slides: Lecture 1.
Thu, Jun 28 Nondeterminism and Epsilon Transitions.

[MS05] Chapter 1.

Slides: Lecture 2.
Tue, Jul 03 Regular Expressions and Language Properties.

[MS05] Chapter 1.

Slides: Lecture 3.
Thu, Jul 05 The Pumping Lemma and Closure Properties.

[MS05] Chapter 1.

Slides: Lecture 4.
Tue, Jul 10 Homomorphisms and Efficient State Minimization.

[MS05] Chapter 1.

Slides: Lecture 5.
Thu, Jul 12 Context-Free Languages and Parse Trees.

[MS05] Chapter 2.

Slides: Lecture 6.
Tue, Jul 17 Ambiguous Grammars and Compactification.

[MS05] Chapter 2.

Slides: Lecture 7.
Thu, Jul 19 Normal Forms and Pushdown Automata.

[MS05] Chapter 2.

Slides: Lecture 8.
Tue, Jul 24 Equivalence of CFG's and PDA's.

[MS05] Chapter 2.

Slides: Lecture 9.
Thu, Jul 26 Midterm.
Thu, Aug 02 Pumping Lemma and Closure Properties of CFL's.

[MS05] Chapter 2.

Slides: Lecture 10.
Tue, Aug 07 Enumerations and Turing Machines.

[MS05] Chapter 3.

Slides: Lecture 11.
Thu, Aug 09 Decidability.

[MS05] Chapter 4.

Slides: Lecture 12.
Tue, Aug 14 NP-Completeness and Boolean Satisfiability.

[MS05] Chapter 5.

Slides: Lecture 13.
Sat, Aug 18 Final.

References

[MS05]Michael Sipser. Introduction to The Theory of Computation. Course Technology, 2nd edition, 2005.
[HMU06]John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison Wesley, 3rd edition, 2006.

Template credit goes to Dmitriy Morozov.