CIS 480 - Computer Theory - Spring 2000
HOMEWORK #1
DUE: Wednesday, February 9th, Beginning of Class

Turn in this assignment on-paper; hand-drawings will be fine!

1. Draw the state diagram of a DFA that accepts all strings from the 
alphabet {0,1} that begin with a 1 and end with a 1.

2. Draw the state diagram of a DFA that accepts all strings from the 
alphabet 
{0, 1} that contain three consecutive 0's anywhere within them.

3. Draw the state diagram of a DFA that accepts all strings from the 
alphabet {0,1} that contain at least three 0's within them (they need not 
be consecutive, note!)

4. Draw the state diagram of a DFA that accepts only strings from the 
alphabet 
{0, 1} in which there are NOT at least three 0's within them (only 
strings with zero, one, or two 0's are in this language).

5. Choose one of your answers to 1-4. Indicate your choice, and express 
your DFA for that problem in the formal 5-tuple notation for a DFA.

6. Draw the "tree of possibilities" (as demonstrated in lecture, or in 
Figure 1.16 on p. 50) for the string 01101 for the following NFA:

7. Is 01101 accepted by the NFA depicted in problem 6? How can you tell, 
from the tree of possibilities?

8. Draw an NFA (that is NOT also a DFA) that accepts all strings from the 
alphabet {0, 1} containing a 0 in either the third or second position 
from the end.