# 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

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