Question

Consider the NFA N with states labeled q1, q2 and q3, where q1 is the start state and q2 and q3 are the final (accepting) states.

The transition function for N is δ(q1,a) = {q1}, δ(q1,b) = {q1,q2},  δ(q2,a) = {q3}, δ(q2,b)= ∅, δ(q3,a)= ∅, and δ(q3,b)= ∅.

Let L be the language recognized by N i.e. L(N).

a) Draw the state diagram for N.

b) Describe in plain English what's in the language L.

c) Via the construction NFA to DFA, draw the state diagram for a DFA corresponding to the NFA. Your DFA should recognize the same language L that the NFA recognizes. Remember, each state of your DFA will be labeled by a set of states from the original NFA.

Give a regular expression that describes L. You don't need to use any particular method to get the regular expression. (It's OK to just write the expression without justification.)

Answer 1