ICS 162, Fall 2003:
Formal Languages and Automata Theory

General Course Information

Coursework will consist of weekly homeworks, a midterm, and a comprehensive final exam. The course letter grade will be determined on a curve, combining numerical scores for homeworks (15%), midterm (35%), and final (50%). 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, 9:30 - 10:50 in CS 180. I will be available for office hours Mondays and Wednesdays 2:00 - 3:00 in my office, CS 358D. The TA for the course is Kevin Wortman <kwortman@ics.uci.edu>. Kevin's office hours will be Mondays 1:00 - 2:00 and Thursdays 3:00 - 4:00 in CST 124, the office down the hall from the distribution center.

Tentative Schedule

• Week 1: Finite automata and regular expressions. Peg-solitaire example. [1.1, 1.3].
  Homework due Tuesday, October 7: ex. 1.4, 1.13, 1.15
• Week 2: Nondeterminism, equivalence of automata and expressions, and closure properties. Garden-of-Eden example. [1.2, 1.3].
  Homework due Tuesday, October 14: ex. 1.14, 1.16; pr. 1.24, 1.26
• Week 3: Nonregular languages. Context free grammars. [1.4, 2.1]
  Homework due Tuesday, October 21: ex. 1.17, 1.18, 2.4, 2.9
• Week 4: Pushdown automata and context free parsing algorithms. Non-context-free languages. [2.2, 2.3]
  Homework due Tuesday, October 28: 2.2, 2.14, 2.18
• Week 5: MIDTERM TUESDAY. Turing machine and RAM models. Church-Turing thesis. [3.1,3.2]
  Homework due Tuesday, November 4: 3.1, 3.8(b,c)
• Week 6: Universal Turing machines and cellular automata. [3.3]
  Homework due Thursday, November 13: 3.5, 3.9, 3.13, 3.19
• Week 7: VETERANS DAY TUESDAY. Undecidability and reduction. [4,5]
  Homework due Tuesday, November 18: 4.3, 4.5, 4.21
• Week 8: P, NP, NP-completeness [7.1 - 7.3; 7.4]
  Homework due Tuesday, November 25: 7.6, 7.7, 7.8, 7.11
• Week 9: More NP-completeness [7.5]; THANKSGIVING THURSDAY.
• Week 10: Space complexity; complexity of games [8.1, 8.2, 8.3 8.6]

Other Course-Related Information

• Final exam from Spring 2001.
• Python implementation of conversions between regular expressions, DFAs, and NFAs, closure properties of regular languages, and decision algorithms for regular language equality and containment.
• Midterm from Fall 2003 -- Solutions
• Time-space diagram of example evolution for Turing-complete cellular automaton Rule 110
• Syllabus and final exam from Spring 1991.
• Computational complexity of games and puzzles.
• The Game of Life.
• The Busy Beaver problem.