Let M

_{N}= (Q_{N}, Σ_{N}, δ_{N}, q_{0}, 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_{0}, 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_{0}(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:- δ
_{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.- Add the state [q
_{l}, q_{m},….q_{n}] to Q_{D}, if it is not already in Q_{D}. - 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

_{0}of DFA is made the final state.
## No comments:

## Post a Comment