Equivalence of DFAs and NFAs

Theorem: For every nondeterministic finite automaton, there exists a deterministic finite automaton that recognizes the same language. Thus, the class of languages recognized by DFAs and NFAs is the same.

Conversion of ε-NFAs to NFAs

Lemma: For every ε-NFA, there exists an NFA without ε-transitions that recognizes the same language.

A Helpful Concept: ε-closure

The ε-closure of a state P is the set of states reachable from state P only taking ε-transitions.

• P ∈ ε-closure(P). A state is always reachable from itself.
• If Q ∈ ε-closure(P) and δ(Q, ε) = R, then R ∈ ε-closure(P).

For example, consider the following NFA.

The ε-closure of each state is:

• ε-closure(q₀) = { q₀ }
• ε-closure(q₁) = { q₁, q₂, q₃ }
• ε-closure(q₂) = { q₂, q₃ }
• ε-closure(q₃) = { q₃ }

Suppose the NFA is in state q₁. If a "1" is read, it undergoes a transition to state q₂. However, this is not the only state reachable reading only one symbol. Any state in ε-closure(q₁) is reachable before reading the symbol.
Consider the set { δ(q, 1) | q ∈ ε-closure(q₁) }, or "the set of all states reachable from ε after reading the symbol "1".
From this set, more states can be reached without reading any more input symbols. The union of the ε-closure of all states in this set are all of the states reachable after reading a "1" from state q₁.

Consider for any state q and symbol "a" the transition δ(q, ε*aε*), where the word "ε*aε*" denotes an arbitrary number of ε-transitions followed by a single "a" followed by another arbitrary number of ε-transitions.
This transition represents the ε-closure of all states reachable from ε-closure(q) after reading the symbol "a".

For example: δ(q₁, ε*1ε*) = δ(q₁, 1ε*) ∪ δ(q₂, 1ε*) ∪ δ(q₃, 1ε*)

• δ(q₁, 1ε*) = ∅
• δ(q₂, 1ε*) = δ(q₂, ε) = ε-closure(q₂) = { q₂, q₃ }
• δ(q₃, 1ε*) = ∅

δ(q₁, ε*1ε*) = ∅ ∪ { q₂, q₃ } ∪ ∅ = { q₂, q₃ }

This is a complete set of states reachable from q₁ after only reading the symbol "1".

To convert an ε-NFA to an NFA without ε-transitions, simply determine this transition for every state-symbol pair.

	0	1
q0	{ q0 }	{ q1, q2, q3 }
q1	{ q1, q2, q3 }	{ q2, q3 }
q2	∅	{ q2, q3 }
q3	∅	∅

This table represents the transitions in the equivalent NFA without ε-transitions.

Conversion of NFAs to DFAs

The items in the new transition table are sets of states in the powerset of Q = { q₀, q₁, q₂, q₃ }. These sets can be treated as labels for new states. Begin with all of the states reachable from the initial state q₀.

Now we must find the union of all states reachable from { q₁, q₂, q₃ } after reading symbols "0" and "1".

• δ(q₁, 0) = { q₁, q₂, q₃ }
• δ(q₂, 0) = ∅
• δ(q₃, 0) = ∅

• δ(q₁, 1) = { q₂, q₃ }
• δ(q₂, 1) = { q₂, q₃ }
• δ(q₃, 1) = ∅

This indicates from state { q₁, q₂, q₃ } a self-loop on symbol "0" and a transition to a new state { q₂, q₃ } on symbol "1".

The process is repeated for the new state { q₂, q₃ }.
The previously observed transitions can be reused.

• δ(q₂, 0) = ∅
• δ(q₃, 0) = ∅

• δ(q₂, 1) = { q₂, q₃ }
• δ(q₃, 1) = ∅

This indicates from state { q₂, q₃ } a self-loop on symbol "1" and a transition to a dead state ∅ on symbol "0".

Now the DFA is not missing any transitions, it is missing final states.
q₃ was the only final state in the original NFA.
All states containing q₃ are marked final.