SKEDSOFT

Introduction: Conversion of The NFA simplifies computational design, but the use of nondeterministic selections and ǫ-transitions makes it look very different from FA.An NFA for a language can be smaller and easier to construct than a DFA.

A Greedy Conversion Algorithm

Step 1:  For each state p ∈ Q and for each symbol a ∈Σ, compute the set R(p, a) of all states that can be reached from state p by:

(a) any number of ǫ transitions,

(b) one transition labeled by a, and then

(c) any number of ǫ transitions.

Step 2:  Initialize the state collection S as {p0}, where p0 is the set of all states that can be reached from q0 by following any number of ǫ transitions.

Step 3:  While S contains a state with no outgoing edges, select an arbitrary member, say r, of S, and do the following:

• For each symbol a, compute the state ra as ∪q∈rR(q, a), add ra to S if ra is not already in it, and then draw an arc from r to ra.

Algorithm Execution Example:

Step 2: Initially S = {{q1}}.

Step 3: {q1} on 0 changes the state to {q1}

{q1} on 1 changes the state to {q1, q2, q3}. New!

{q1, q2, q3} on 0 changes the state to {q1, q3, q4}. New!

{q1, q2, q3} on 1 changes the state to {q1, q2, q3, q4}. New!

{q1, q3, q4} on 0 changes the state to {q1, q4}. New!

{q1, q2, q3} on 1 changes the state to {q1, q2, q3, q4}.

{q1, q2, q3, q4} on 0 changes the state to {q1, q3, q4}.

{q1, q2, q3, q4} on 1 changes the state to {q1, q2, q3, q4}.

{q1, q4} on 0 changes the state to {q13}.

{q1, q4} on 1 changes the state to {q1, q2, q3}.