The Steam Powered Turing Machine University of Washington Department of Computer Science & Engineering
 CSE 322: Introduction to Formal Models in Computer Science, Spring 2007
  CSE Home   CSE 322 Home  About Us    Search    Contact Info 

  Sign-up Instructions
Homework Assignments
  Homework 1 (Due April 6th)
  Homework 2 (Due April 13th)
  Homework 3 (Due April 20th)
  Homework 4 (Due April 27th)
  Homework 5 (Due May 18th)
  Homework 6 (Due May 25th)
  Homework 7 (Due June 1st)
Reading Assignments
  Review Chapter 0
  Sections 1.1, 1.2
  Sections 1.2, 1.3
  Converting DFAs to Reg.Exps.
  Section 1.4
  The Myhill-Nerode Theorem.
  DFA Minimization.
  Pattern Matching.
  Homework Policy
MWF 1:30-2:20   

Office Hours Location Phone
Instructor: Parikshit Gopalan   parik at cs  
Th 4:30-5:30
CSE 438 616-6892
TAs: Widad Machmouchi    widad at cs  
Th 1:30-2:30
CSE 678
Jean Wu   jeaneis at cs  
T 1:30-2:30
CSE Atrium


Michael Sipser, Introduction to the Theory of Computation. Either the first or second editions will work. Although the numbering of almost everything in the two editions is different, the content is mostly unchanged except that the second edition contains some new and solved problems. The international edition content is also OK though the problem numbers may differ from both U.S. editions. (Second edition errata: first printing. First edition errata: first printing , later printings .)

Mailing List

There is a class mailing list, cse322. Follow the link in the left column on this page to sign up. Everyone is expected to be reading cse322 e-mail to keep up-to-date on the course.


Homework 45-55%, midterm 15-20%, final 30-35%, give or take. Extra Credit.


Will be given in class on Friday May 4th. Syllabus is all of Regular Languages: DFAs, NFAs, regular expressions, closure properties, pumping lemma, Myhill-Nerode, state minimization, pattern matching using DFAs.


The final exam is from 2:30-4:20 p.m. on Monday, Jun. 4, 2007, in class.

The exam will consist of 7 questions. One true or false question (no explanation needed), and two questions on DFAs, PDAs and Turing machines respectively. For the syllabus and more on what kinds of questions to expect, read this!

Here is a sample final from previous versions of this course. Do go through it and try the questions, we will discuss them in class this Friday. For Turing machines,go through all the homework problems (even the ones you havent turned in) and the problems from Chapter 4 of Sipser. Solutions to Hw7 will be handed out in class on Friday, we will also discuss them briefly if time permits.

Finally, extra office hours in CSE-438 from 4:30-5:30 on Friday.

solution for homework 3

Portions of the CSE 322 Web may be reprinted or adapted for academic nonprofit purposes, providing the source is accurately quoted and duly credited. The CSE 322 Web: © 1993-2007, Department of Computer Science and Engineering, University of Washington.