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.)
-
Exercise 1.6 on page 84 of your textbook.
-
Exercise 1.7 on page 84 of your textbook.
-
Exercise 1.16 on page 86 of your textbook.
-
Exercise 1.24 on page 87 of your textbook.
-
Problem 1.31 on page 88 of your textbook.
Hint.
-
Work Problem 1.37 on page 89 of your textbook.
Hint.
-
Work Problem 1.46 on page 90 of your textbook.
-
Construct a minimal DFA equivalent to each NFA.
-
Find a regular expression for the language accepted by each
DFA.