**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.