For every non-deterministic finite automata, there exists an equivalent deterministic finite automata. The equivalence between the two is defined in terms of language acceptance. Since an NFA is a nothing more than a finite automata in which zero, one, or more transitions on an input symbol is permitted, we can always construct a finite automata that will simulate all the moves of the NFA on a particular input symbol in parallel. We then get a finite automata in which there will be exactly one transition on an input symbol; hence, it will be a DFA equivalent to the NFA.
Since the DFA equivalent of the NFA simulates (parallels) the moves of the NFA, every state of a DFA will be a combination of one or more states of the NFA. Hence, every state of a DFA will be represented by some subset of the set of states of the NFA; and therefore, the transformation from NFA to DFA is normally called the "construction" subset. Therefore, if a given NFA has n states, then the equivalent DFA will have 2n number of states, with the initial state corresponding to the subset {q0}. Therefore, the transformation from NFA to DFA involves finding all possible subsets of the set states of the NFA, considering each subset to be a state of a DFA, and then finding the transition from it on every input symbol. But all the states of a DFA obtained in this way might not be reachable from the initial state; and if a state is not reachable from the initial state on any possible input sequence, then such a state does not play role in deciding what language is accepted by the DFA. (Such states are those states of the DFA that have outgoing transitions on the input symbols—but either no incoming transitions, or they only have incoming transitions from other unreachable states.) Hence, the amount of work involved in transforming an NFA to a DFA can be reduced if we attempt to generate only reachable states of a DFA. This can be done by proceeding as follows:
Let M = (Q, Σ, δ, q0, F ) be an NFA to be transformed into a DFA.
Let Q1 be the set states of equivalent DFA.
begin:
Q1old = Φ
Q1new = {q0}
While (Q1old ≠ Q1new)
{
Temp = Q1new - Q1old
Q1 = Q1new
for every subset P in Temp do
for every a in Σdo
If transition from P on a goes to new subset S of Q
then
(transition from P on a is obtained by finding out
the transitions from every member of P on a in a given
NFA
and then taking the union of all such transitions)
Q1 new = Q1 new ∪ S
}
Q1 = Q1new
end
A subset P in Ql will be a final state of the DFA if P contains at least one member of F of the NFA. For example, consider the following finite automata:
where:
The DFA equivalent of this NFA can be obtained as follows:
The transition diagram associated with this DFA is shown in Figure 1.
