Thursday, April 5, 2012

Conversion from NFA to DFA

Let MN = (QN, ΣN, δN, q0, AN) be an NFA and accepts the language L(MN). There should be an equivalent DFA MD = (QD, ΣD, δD, q0, AD) such that L(MD) = L(MN). The procedure to convert an NFA to its equivalent DFA is shown below:

The start state of NFA MN is the start state of DFA MD. So, add q0(which is the start state of NFA) to QD and find the transitions from this state. The way to obtain different transitions is shown in step2.
For each state [qi, qj,….qk] in QD, the transitions for each input symbol in Σ can be obtained as shown below:
  1. δD([qi, qj,….qk], a) = δN(qi, a) U δN(qj, a) U ……δN(qk, a)
= [ql, qm,….qn] say.
  1. Add the state [ql, qm,….qn] to QD, if it is not already in QD.
  2. Add the transition from [qi, qj,….qk] to [ql, qm,….qn] on the input symbol a iff the state [ql, qm,….qn] is added to QD in the previous step.
The state [qa, qb,….qc] QD is the final state, if at least one of the state in qa, qb, ….. qc AN i.e., at least one of the component in [qa, qb,….qc] should be the final state of NFA.
If epsilon () is accepted by NFA, then start state q0 of DFA is made the final state.

No comments:

Post a Comment