ICS 162, Spring 2001:
Formal Languages and Automata Theory

General Course Information

Coursework will consist of biweekly homeworks and a comprehensive final exam. Group work on homeworks is permitted; each student should turn in his or her own copy of the homeworks. The course text will be Introduction to the Theory of Computation, by Michael Sipser (PWS Publishing, 1997). The course meets Tuesdays and Thursdays, 2:00 - 3:20 in ICF 101.

Tentative Schedule

• Week 1: Finite automata and regular expressions. Peg-solitaire example. [1.1, 1.3]
• Week 2: Nondeterminism, equivalence of automata and expressions, and closure properties. Garden-of-Eden example. [1.2, 1.3]
      Homework due Thurs. April 19th: problems 1.4, 1.5, 1.12, 1.15, 1.25.
• Week 3: Nonregular languages. Context free grammars. [1.4, 2.1]
• Week 4: Pushdown automata and context free parsing algorithms. [2.2]
      Homework due Thurs. May 3rd: problems 1.17, 1.18, 2.1, 2.4, 2.14.
• Week 5: Noncontext free languages. Turing machine and RAM models. Church-Turing thesis. [2.3,3.1,3.2]
• Week 6: Universal Turing machines and cellular automata. [3.3]
      Homework due Thurs. May 17th: problems 2.8, 2.18, 3.1, 3.5.
• Week 7: Undecidability and reduction. [4,5]
• Week 8: P, NP, NP-completeness [7.1 - 7.3; 7.4]
• Week 9: More NP-completeness; space complexity [7.5; 8.1, 8.6]
      Homework due Thurs. June 7th: problems 4.4, 5.3, 7.6, 7.11, 7.16.
• Week 10: NO CLASS TUESDAY; complexity of games [8.2, 8.3]

Other Course-Related Information

• Computational complexity of games and puzzles.
• The Game of Life.
• The Busy Beaver problem.