CS 631, Fall 2009


Assignment #5: 10 points

Date Due: Tuesday, 10/13/09


	Read Sections 3.6-3.8.

(2) 1.	Build a DFA which accepts the language of Exercise 3.3.5(f).  Use
	the DFA to solve Exercise 3.3.5(f).

(2) 2.	Exercise 3.5.4.** 

(3) 3.	Use Algorithm 3.20 to convert the NFA of Figure 3.46 to a DFA.

(2) 4.	Exercise 3.7.3(d).  Use Algorithm 3.23 to produce the NFA only.  

(1) 5.  Assume you are given an NFA, R, which accepts a regular expression, r.
        Construct an NFA for r+, where '+' is the Lex operator defined in
        Figure 3.8.


      **For full credit, turn in well commented program listings and the
        output of the computer runs for this problem.