NFA to DFA Conversion

Part III. NFA to DFA Conversion

Consider the following NFA,

In this NFA, from state q₀ there are three possible moves on the input symbol a, namely to q₀, q₁, and q₂. When we simulate this NFA, the move from q₀ on input a is non-deterministic. That means the next state is not uniquely determined by the current state and input symbol. In a deterministic finite automaton (DFA), however, for each state and each input symbol there is exactly one transition. A DFA is easier to simulate because the next state is unambiguous. For every NFA there exists an equivalent DFA that recognises the same language; the conversion procedure constructs such a DFA.

5 Epsilon Closure

Before applying the standard construction from NFA to DFA we must handle epsilon (ε) transitions. The epsilon closure (or ε-closure) of a state is central to that process.

Definition. The epsilon closure of a state q, written ECLOSE(q), is the set containing q itself and every state that can be reached from q by following zero or more ε-transitions.

To compute ECLOSE(q) one may use a depth-first or breadth-first search restricted to ε-transitions: start from q, follow all outgoing ε-transitions to new states, then continue from those states until no new states are discovered.

Example 1

Consider the following NFA.

Find the epsilon closure of all states.

• ECLOSE(1) = {1, 2, 4}
• ECLOSE(2) = {2, 4}
• ECLOSE(3) = {3}
• ECLOSE(4) = {4}

Example 2

Consider the following NFA.

Find the epsilon closure of all states.

• ECLOSE(1) = {1, 2, 3, 6, 4}
• ECLOSE(2) = {2, 3, 6}
• ECLOSE(3) = {3, 6}
• ECLOSE(4) = {4}
• ECLOSE(5) = {5, 7}
• ECLOSE(6) = {6}

Example 3

Consider the following NFA.

Compute the epsilon closure of all states.

• ECLOSE(q₀) = {q₀, q₁, q₂, q₃}
• ECLOSE(q₁) = {q₁, q₂, q₃}
• ECLOSE(q₂) = {q₂, q₃}
• ECLOSE(q₃) = {q₃}

6 Conversion of NFA to DFA

The conversion from an NFA (possibly with ε-transitions) to an equivalent DFA is performed in two main phases:

1. Transform the NFA with ε-transitions to an NFA without ε-transitions (eliminate ε-transitions).
2. Convert the resulting NFA (without ε-transitions) to a DFA using the subset construction (also called the powerset construction).

Both phases are described below with examples and clear step-by-step instructions.

Phase 1 - Eliminate ε-transitions

Given an NFA with ε-transitions, we construct an equivalent NFA without ε by using epsilon closures. The idea is to replace each state by its epsilon closure for transition purposes so that all ε-moves are absorbed into ordinary symbol transitions.

One systematic method:

1. Compute ECLOSE(s) for every state s of the original NFA.
2. For each state p and each input symbol a, compute the set of states reachable by an a-move from any state in ECLOSE(p), then take epsilon closure of that union; that is, δ'(p,a) = ECLOSE(⋃_{q in ECLOSE(p)} δ(q,a)).
3. The start state of the new NFA is ECLOSE(start). Any state whose closure contains an original final state becomes final in the new NFA.

Example 1 (Eliminate ε-transitions)

Consider the NFA with ε-transitions below.

The original states are q₀, q₁, q₂. The start state is q₀. The final state is q₂.

Step a: Find all epsilon closures.

• ECLOSE(q₀) = {q₀, q₁, q₂}
• ECLOSE(q₁) = {q₁, q₂}
• ECLOSE(q₂) = {q₂}

The reachable sets (closures) become the states of the new NFA: {q₀,q₁,q₂}, {q₁,q₂}, {q₂}. The start state is {q₀,q₁,q₂} because it is ECLOSE(start). Any of these new states that include the original final state q₂ are final.

Next find transitions of these new states on input symbols a, b, c. For example, consider the composite state {q₀,q₁,q₂} and determine where an input a, b, or c can lead by following the above algorithm.

After computing these transitions we obtain the NFA without ε-transitions.

Rename the composite states for convenience:

• {q₀, q₁, q₂} as q_x
• {q₁, q₂} as q_y
• {q₂} as q_z

The transition diagram of the new NFA is shown below. Note that in this particular case the resulting NFA without ε-transitions already satisfies the DFA property (one transition per symbol from each state).

Phase 2 - Subset Construction (NFA without ε to DFA)

After eliminating ε-transitions we apply the subset construction:

1. The start state of the DFA is the epsilon closure of the start state of the original NFA (or simply the start state of the NFA without ε if you already removed ε).
2. For each unprocessed DFA state S (S is a set of NFA states) and for each input symbol a, compute T = ⋃_{q in S} δ(q,a). If ε-transitions remain in your NFA you should take ECLOSE(T). T becomes a DFA state (possibly previously seen).
3. Repeat until no new DFA state is generated.
4. A DFA state S is accepting if S contains at least one accepting state of the original NFA.

Example 2 (Full conversion)

Convert the following NFA to a DFA.

Step 1: This NFA has no ε-transitions, so we proceed directly to the subset construction.

Step a: Start with the start state q₀.

• δ(q₀, a) = {q₀, q₁}
• δ(q₀, b) = {q₀}

We have a new DFA state {q₀, q₁}.

Step b: Consider {q₀, q₁}.

• δ({q₀, q₁}, a) = δ(q₀, a) ∪ δ(q₁, a) = {q₀, q₁} ∪ {q₂} = {q₀, q₁, q₂}
• δ({q₀, q₁}, b) = δ(q₀, b) ∪ δ(q₁, b) = {q₀} ∪ {q₁} = {q₀, q₁}

We have a new DFA state {q₀, q₁, q₂}.

Step c: Consider {q₀, q₁, q₂}.

• δ({q₀, q₁, q₂}, a) = δ(q₀, a) ∪ δ(q₁, a) ∪ δ(q₂, a) = {q₀, q₁} ∪ {q₂} ∪ {q₃} = {q₀, q₁, q₂, q₃}
• δ({q₀, q₁, q₂}, b) = δ(q₀, b) ∪ δ(q₁, b) ∪ δ(q₂, b) = {q₀} ∪ {q₁} ∪ {q₃} = {q₀, q₁, q₃}

We obtain two new DFA states {q₀, q₁, q₂, q₃} and {q₀, q₁, q₃}.

Step d: Process each of these newly generated states.

For {q₀, q₁, q₂, q₃} compute transitions (details shown below).

For {q₀, q₁, q₃} compute transitions (details shown below).

No further new states are generated. The transition table for the completed DFA is shown below. The start state is q₀. DFA final states are those composite states that contain at least one final state of the original NFA (here q₂ or q₃).

• Final DFA states: {q₀, q₁, q₂}, {q₀, q₁, q₂, q₃}, {q₀, q₁, q₃}

Rename these DFA states for compactness:

• q₀ as A
• {q₀, q₁} as B
• {q₀, q₁, q₂} as C
• {q₀, q₁, q₂, q₃} as D
• {q₀, q₁, q₃} as E

The diagram shows a DFA because from each state there is exactly one transition for each input symbol.

Example 3

Convert the following NFA to DFA.

Step 1: This NFA contains no ε-transitions, so proceed directly to subset construction.

From the start state q₀:

• δ(q₀, a) = {q₀, q₁}
• δ(q₀, b) = {q₂}

Generate new composite states and compute their transitions. Intermediate tables/diagrams are shown below.

No more new states are generated. The start state is q₀. Final states are q₂ and {q₁, q₂} because they contain the original final state q₂.

Rename composite states for convenience:

• q₀ as A
• {q₀, q₁} as B
• {q₁, q₂} as C
• q₂ as D

Example 4

Consider the NFA below. Convert it to a DFA.

Step 1: Eliminate ε-transitions by computing closures.

• ECLOSE(q₀) = {q₀, q₁, q₂}
• ECLOSE(q₁) = {q₁, q₂}
• ECLOSE(q₂) = {q₂}

The states of the new NFA are the closures above; the start state is {q₀, q₁, q₂}. Any closure that contains the original final state q₂ becomes final in the new NFA.

Now find transitions of these closures on input symbols 0 and 1. For example, consider closure {q₀, q₁, q₂} and compute its transitions:

Rename closures as:

• {q₀, q₁, q₂} as A
• {q₁, q₂} as B
• {q₂} as C

The NFA without ε-transitions shown above is already a DFA because from each state there is exactly one transition for each input symbol.

Example 5

Consider the following NFA. Convert it to a DFA.

Step 1: This NFA contains no ε-transitions, so proceed to the subset construction.

Begin from the start state q₁:

• δ(q₁, a) = {q₁, q₂}
• δ(q₁, b) = {q₁}

Continue computing transitions for newly generated composite states:

The start state is q₁. The DFA accepting state is {q₁, q_f} because it contains the original final state q_f. Rename states:

• q₁ as A
• {q₁, q₂} as B
• {q₁, q_f} as C

The resulting machine is a DFA because every state has exactly one transition for each input symbol.

Exercises

1. Convert the following NFA to DFA.

2. Convert the following NFA to DFA.

3. Convert the following NFA to DFA.