Conversion from NFA to DFA

Let M_N = (Q_N, Σ_N, δ_N, q₀, A_N) be an NFA and accepts the language L(M_N). There should be an equivalent DFA M_D = (Q_D, Σ_D, δ_D, q₀, A_D) such that L(M_D) = L(M_N). The procedure to convert an NFA to its equivalent DFA is shown below:

Step1:

The start state of NFA M_N is the start state of DFA M_D. So, add q₀(which is the start state of NFA) to Q_D and find the transitions from this state. The way to obtain different transitions is shown in step2.

Step2:

For each state [q_i, q_j,….q_k] in Q_D, the transitions for each input symbol in Σ can be obtained as shown below:

1. δ_D([q_i, q_j,….q_k], a) = δ_N(q_i, a) U δ_N(q_j, a) U ……δ_N(q_k, a)

= [q_l, q_m,….q_n] say.

2. Add the state [q_l, q_m,….q_n] to Q_D, if it is not already in Q_D.
3. Add the transition from [q_i, q_j,….q_k] to [q_l, q_m,….q_n] on the input symbol a iff the state [q_l, q_m,….q_n] is added to Q_D in the previous step.

Step3:

The state [q_a, q_b,….q_c] ∈ Q_D is the final state, if at least one of the state in q_a, q_b, ….. q_c ∈ A_N i.e., at least one of the component in [q_a, q_b,….q_c] should be the final state of NFA.

Step4:

If epsilon (∈) is accepted by NFA, then start state q₀ of DFA is made the final state.