NFA - DFA Equivalence

In principle, every NFA can be turned into an equivalent DFA. The basic idea is that when a transition results in a set of states, we treat the set as one state in the equivalent DFA.

Lets work this out for the above example. We will systematically uncover new states and transitions from the NFA and add them to the DFA.

Start state = q₀

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

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

δ({q₀, q₂}, a) = δ(q₀, a) U δ(q₂, a) = {q₀, q₁} U φ = {q₀, q₁}
δ({q₀, q₁}, b) = δ(q₀, b) U δ(q₂, b) = {q₀} U {q₃} = {q₀, q₃}

δ({q₀, q₃}, a) = δ(q₀, a) U δ(q₃, a) = {q₀, q₁} U φ = {q₀, q₁}
δ({q₀, q₃}, b) = δ(q₀, b) U δ(q₃, b) = {q₀} U φ = q₀

What is the final state of the equivalent DFA?

Since q₃ is the final state in the original NFA, the states which contain q₃ in the equivalent DFA are the final states. In this example, it is {q₀, q₃}

Can you now the see the similarity between this against the DFA that was designed directly?

How many states will the equivalent DFA have at the maximum?

2ⁿ where n is the number of states in the original NFA. This is so, because the equivalent DFA may contain, at worst, every combination of the states of the original NFA.

{
φ,
{q₀}, {q₁}, {q₂}, {q₃},
{q₀, q₁}, {q₀, q₂}, {q₀, q₃}, {q₁, q₂}, {q₁, q₃}, {q₂, q₃},
{q₀, q₁, q₂}, {q₀, q₁, q₃}, {q₁, q₂, q₃},
{q₀, q₁, q₂, q₃}
}

Convert the NFAs obtained in the previous page to their equivalent DFAs.

2. NFA that accepts strings that does not contain abb. Σ = {a, b}

This is left as exercise.

3. NFA that accepts strings that starts with two a's and ends with two a's. Σ = {a, b}

Try on your own first. Check here for the NFA.

4. NFA that accepts strings that end with "ab" or "ba". Σ = {a, b}

This is left as exercise.

5. NFA that accepts strings that starts and ends with different symbols Σ = {a, b}

This is left as an exercise.

ε-NFA to DFA

The next question is: can we convert ε-NFA to an equivalent DFA?

Yes. It is possible. This is shown for the Example 4A. The problem and the ε-NFA obtained are given below.

4A. ε-NFA that accepts strings that end with "ab" or "ba". Σ = {a, b}

Step 1: Start state = {q₀, q₁, q₄}, since ε transitions from q₀ leads to q₁ and q₄ and can be combined.

Note that whichever state contains q₀ will also include q₁ and q₄ since ε-transitions are possible to these two states in the original ε-NFA.

Step 2: Transitions from the start state

δ({q₀, q₁, q₄}, a) = δ(q₀, a) U δ(q₁, a) U δ(q₄, a) = φ U {q₁, q₂} U {q₄} = {q₁, q₂, q₄}

δ({q₀, q₁, q₄}, b) = δ(q₀, b) U δ(q₁, b) U δ(q₄, b) = φ U {q₁} U {q₄, q₅} = {q₁, q₄, q₅}

Step 3: Transitions from state {q₁, q₂, q₄}

δ({q₁, q₂, q₄}, a) = δ(q₁, a) U δ(q₂, a) U δ(q₄, a) = {q₁, q₂} U φ U {q₄} = {q₁, q₂, q₄}

δ({q₁, q₂, q₄}, b) = δ(q₁, b) U δ(q₂, b) U δ(q₄, b) = φ U {q₁} U {q₃, q₇} U {q₄, q₅} = {q₁, q₃ q₇, q₄, q₅}

Note: Whichever state contains q₃ will also include q₇ since ε-transition to q₇ is possible in the original ε-NFA.

Step 4: Transitions from state {q₁, q₄, q₅}

δ({q₁, q₄, q₅}, a) = δ(q₁, a) U δ(q₄, a) U δ(q₅, a) = {q₁, q₂} U {q₄} U {q₅, q₇} = {q₁, q₂, q₄, q₅, q₇}

δ({q₁, q₄, q₅}, b) = δ(q₁, b) U δ(q₄, b) U δ(q₅, b) = {q₁} U {q₄, q₅} U φ = {q₁, q₄, q₅}

Note: Whichever state contains q₆ will also include q₇ since ε-transition to q₇ is possible in the original ε-NFA.

Steps 5 and 6 Transitions from {q₁, q₃ q₇, q₄, q₅} and {q₁, q₂, q₄, q₅, q₇} can be computed in a similar fashion.

5A. ε-NFA that accepts strings that starts and ends with different symbols Σ = {a, b}

This can be done in a similar fashion and is left as an exercise.

ε-NFA is used in converting regular expressions (next topic) to DFA as an intermediate step.

Formal Languages and Automata