FOR FREE CONTENT

NFA to DFA Conversion

Every DFA is NFA but every NFA is not DFA because transition function is not total for NFA.

Now we can convert NFA to DFA.

So, power of DFA and NFA is same because if we convert one machine to another machine then we can both machine has same power.

We consider a NFA which has a language : set of all strings where second last bit is 1 i.e. LRE (0 + 1)*1(0 + 1) (here last bit may be 0 or 1 and second last must be 1, at first of string it may be any combination of 0 or 1). 

Now convert to DFA

Now consider  transition function table of above NFA machine:

Note: at DFA transition function we can go at most at one state, because it does not create multiple copy of machine i.e. we merge the state  ${\mathit{q}}_{\mathbf{0}}{\mathit{q}}_{\mathbf{1}}$to $\mathbf{\left[}{\mathit{q}}_{\mathbf{0}}{\mathit{q}}_{\mathbf{1}}\mathbf{\right]}$  and treated as single state.

Transition is going on until there are no new states. Now $\mathbf{\left(}{\mathit{q}}_{\mathbf{0}}{\mathit{q}}_{\mathbf{2}}\mathbf{\right)}$, $\mathbf{\left(}{\mathit{q}}_{\mathbf{0}}{\mathit{q}}_{\mathbf{1}}{\mathit{q}}_{\mathbf{2}}\mathbf{\right)}$ are final state, because we take those state as final where the final state of NFA ${\mathit{q}}_{\mathbf{2}}\mathbf{ }$is present.

If  NFA consists N states then how many state present at DFA. 

See what are, ${\mathit{q}}_{\mathbf{0}}{\mathit{q}}_{\mathbf{1}}$, $\mathbf{\left[}{\mathit{q}}_{\mathbf{0}}{\mathit{q}}_{\mathbf{2}}\mathbf{\right]}$, $\mathbf{\left[}{\mathit{q}}_{\mathbf{0}}{\mathit{q}}_{\mathbf{1}}{\mathit{q}}_{\mathbf{2}}\mathbf{\right]}\mathbf{ }$etc is subset (combination) of  ${\mathit{q}}_{\mathbf{0}}\mathbf{,}\mathbf{ }{\mathit{q}}_{\mathbf{1}}\mathbf{,}\mathbf{ }{\mathit{q}}_{\mathbf{2}}$ i.e. $\mathbf{\left\{}{\mathit{q}}_{\mathbf{0}}{\mathit{q}}_{\mathbf{1}}{\mathit{q}}_{\mathbf{2}}\mathbf{\right\}}$ is set and all combination is a subset then how many subset or combination is possible is:  ${\mathbf{2}}^{\mathbf{3}\mathbf{ }}\mathbf{=}\mathbf{ }\mathbf{8}\mathbf{ }\mathbf{=}\mathbf{ }{\mathbf{2}}^{\mathbf{\left|}\mathbf{Q}\mathbf{\right|}}$. 

So, maximum number of state of DFA (where NFA has Q states) is ${\mathbf{2}}^{\mathbf{\left|}\mathbf{Q}\mathbf{\right|}}$ .

Design corresponding DFA from NFA:

Now we design DFA from final transition function table converted from NFA transition function table.

Note: After design DFA from NFA, minimum states of DFA depends on NFA, it is redundant or not.

Example:

Generally number of states of DFA converted from NFA is big compare to NFA. But not all the time its true consider example below where DFA states is lesser compare to NFA.

NFA of  language L = (0 + 1)*  i.e. set of all string generated by 0 and 1.   

So, we can say if we construct from NFA to DFA 

            The minimum state of DFA is 1 and the maximum state of DFA is ${\mathbf{2}}^{\mathbf{\left|}\mathbf{Q}\mathbf{\right|}}$

One Initial State

Generally in NFA and DFA has only one starting state. But there can be more than one final state is present. If there is more than one starting state is there, then it is called transition diagram.

If there is more than one starting state at transition diagram then how we convert from NFA to DFA

Example:

First of all this is not a NFA, it is a transition diagram; in that case we merge all starting state and make a single starting state. After that we can convert it to corresponding DFA.