1  (40 points) Consider the following NFAs (a) and (b) below:

a

1

a,b

2

(a)

e

2

a

a

b

(b)

Answer the following questions:

(a)  (5 points) Give a formal definition of the NFA (a)

(b)  (10 points) As discussed in class, every NFA has an equivalent DFA. Give the for-

mal definition of the DFA A (equivalent to NFA (a)) according to the construction given in Theorem 1.39.

(c)  (5 points) Draw the state diagram of the DFA A.

(d)  (5 points) Give a formal definition of the NFA (b)

(e)  (10 points) As discussed in class, every NFA has an equivalent DFA. Give the for-

mal definition of the DFA B (equivalent to NFA (b)) according to the construction given in Theorem 1.39.

(f)  (5 points) Draw the state diagram of the DFA B .

2  (18 points n 2 points per question) For each of the following languages, give two

strings that are members and two strings that are ott members—a total of four strings for each part. Assume the alphabet Σ = {a, b} in all parts.

a.  a*b*

b.  a(ba)*b

c.  a* n b*

d.  (aaa)*

e.  Σ* aΣ*bΣ* aΣ*

f.  aba n bab

g.  (ε n a)b

h.  (a n ba n bb)Σ*