Formal Languages and Automata Theory

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.

- 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]

- 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.

David Eppstein, Dept. Information & Computer Science, UC Irvine, 30 March 2001.