University of Nevada Las Vegas
Howard R. Hughes College of Engineering
School of Computer Science
My Home Page

CSC 456/656 Study Problems

Revised September 28, 2005

The problem given here are not "challenge problems," but are exercises that you should be able to do if you understand the material of the course. They are not to be handed in.
The textbook referred to in the problems is Introduction to the Theory of Computation, by Michael Sipser. PWS. ISBN 0-534-95097-3.
I suggest trying to work each problem without looking at the hints, unless you get stuck. (But don't give up too soon.)
  1. Exercise 1.6 on page 84 of your textbook.
  2. Exercise 1.7 on page 84 of your textbook.
  3. Exercise 1.16 on page 86 of your textbook.
  4. Exercise 1.24 on page 87 of your textbook.
  5. Problem 1.31 on page 88 of your textbook. Hint.
  6. Work Problem 1.37 on page 89 of your textbook. Hint.
  7. Work Problem 1.46 on page 90 of your textbook.
  8. Construct a minimal DFA equivalent to each NFA.
  9. Find a regular expression for the language accepted by each DFA.