Home Â» Automata Conversion from NFA with null to DFA

# Conversion from NFA with Îµ to DFA

Non-deterministic finite automata(NFA) is a finite automata where for some cases when a specific input is given to the current state, the machine goes to multiple states or more than 1 states. It can contain Îµ move. It can be represented as M = { Q, âˆ‘, Î´, q0, F}.

Where

NFA with âˆˆ move: If any FA contains Îµ transaction or move, the finite automata is called NFA with âˆˆ move.

Îµ-closure: Îµ-closure for a given state A means a set of states which can be reached from the state A with only Îµ(null) move including the state A itself.

## Steps for converting NFA with Îµ to DFA:

Step 1: We will take the Îµ-closure for the starting state of NFA as a starting state of DFA.

Step 2: Find the states for each input symbol that can be traversed from the present. That means the union of transition value and their closures for each state of NFA present in the current state of DFA.

Step 3: If we found a new state, take it as current state and repeat step 2.

Step 4: Repeat Step 2 and Step 3 until there is no new state present in the transition table of DFA.

Step 5: Mark the states of DFA as a final state which contains the final state of NFA.

### Example 1:

Convert the NFA with Îµ into its equivalent DFA.

Solution:

Let us obtain Îµ-closure of each state.

Now, let Îµ-closure {q0} = {q0, q1, q2} be state A.

Hence

`Î´'(A, 0) = Îµ-closure {Î´((q0, q1, q2), 0) }  Â  Â  Â  Â  Â  Â  Â  = Îµ-closure {Î´(q0, 0) âˆª Î´(q1, 0) âˆª Î´(q2, 0) }  Â  Â  Â  Â  Â  Â  Â  = Îµ-closure {q3}  Â  Â  Â  Â  Â  Â  Â  = {q3} Â  Â  Â   Â  Â  call it as state B.    Î´'(A, 1) = Îµ-closure {Î´((q0, q1, q2), 1) }  Â  Â  Â  Â  Â  Â  Â  = Îµ-closure {Î´((q0, 1) âˆª Î´(q1, 1) âˆª Î´(q2, 1) }  Â  Â  Â  Â  Â  Â  Â  = Îµ-closure {q3}  Â  Â  Â  Â  Â  Â  Â  = {q3} = B.  `

The partial DFA will be

Now,

`Î´'(B, 0) = Îµ-closure {Î´(q3, 0) }  Â  Â  Â  Â  Â  Â  Â  = Ï•  Î´'(B, 1) = Îµ-closure {Î´(q3, 1) }  Â  Â  Â  Â  Â  Â  Â  = Îµ-closure {q4}  Â  Â  Â  Â  Â  Â  Â  = {q4} Â  Â  Â   Â  Â  i.e. state C  `

For state C:

The DFA will be,

### Example 2:

Convert the given NFA into its equivalent DFA.

Solution: Let us obtain the Îµ-closure of each state.

Now we will obtain Î´â€™ transition. Let Îµ-closure(q0) = {q0, q1, q2} call it as state A.

`Î´'(A, 0) = Îµ-closure{Î´((q0, q1, q2), 0)}  Â  Â  Â  Â  Â  Â  Â  = Îµ-closure{Î´(q0, 0) âˆª Î´(q1, 0) âˆª Î´(q2, 0)}  Â  Â  Â  Â  Â  Â  Â  = Îµ-closure{q0}  Â  Â  Â  Â  Â  Â  Â  = {q0, q1, q2}    Î´'(A, 1) = Îµ-closure{Î´((q0, q1, q2), 1)}  Â  Â  Â  Â  Â  Â  Â  = Îµ-closure{Î´(q0, 1) âˆª Î´(q1, 1) âˆª Î´(q2, 1)}  Â  Â  Â  Â  Â  Â  Â  = Îµ-closure{q1}  Â  Â  Â  Â  Â  Â  Â  = {q1, q2} Â  Â  Â  Â  call it as state B    Î´'(A, 2) = Îµ-closure{Î´((q0, q1, q2), 2)}  Â  Â  Â  Â  Â  Â  Â  = Îµ-closure{Î´(q0, 2) âˆª Î´(q1, 2) âˆª Î´(q2, 2)}  Â  Â  Â  Â  Â  Â  Â  = Îµ-closure{q2}   Â  Â  Â  Â  Â  Â  Â  = {q2} Â  Â  Â  Â  call it state C  `

Thus we have obtained

The partial DFA will be:

Now we will find the transitions on states B and C for each input.

Hence

`Î´'(B, 0) = Îµ-closure{Î´((q1, q2), 0)}  Â  Â  Â  Â  Â  Â  Â  = Îµ-closure{Î´(q1, 0) âˆª Î´(q2, 0)}  Â  Â  Â  Â  Â  Â  Â  = Îµ-closure{Ï•}  Â  Â  Â  Â  Â  Â  Â  = Ï•    Î´'(B, 1) = Îµ-closure{Î´((q1, q2), 1)}  Â  Â  Â  Â  Â  Â  Â  = Îµ-closure{Î´(q1, 1) âˆª Î´(q2, 1)}  Â  Â  Â  Â  Â  Â  Â  = Îµ-closure{q1}  Â  Â  Â  Â  Â  Â  Â  = {q1, q2} Â  Â  Â  Â  i.e. state B itself    Î´'(B, 2) = Îµ-closure{Î´((q1, q2), 2)}  Â  Â  Â  Â  Â  Â  Â  = Îµ-closure{Î´(q1, 2) âˆª Î´(q2, 2)}  Â  Â  Â  Â  Â  Â  Â  = Îµ-closure{q2}  Â  Â  Â  Â  Â  Â  Â  = {q2} Â  Â  Â  Â  i.e. state C itself  `

Thus we have obtained

The partial transition diagram will be

Now we will obtain transitions for C:

`Î´'(C, 0) = Îµ-closure{Î´(q2, 0)}  Â  Â  Â  Â  Â  Â  Â  = Îµ-closure{Ï•}  Â  Â  Â  Â  Â  Â  Â  = Ï•    Î´'(C, 1) = Îµ-closure{Î´(q2, 1)}  Â  Â  Â  Â  Â  Â  Â  = Îµ-closure{Ï•}  Â  Â  Â  Â  Â  Â  Â  = Ï•    Î´'(C, 2) = Îµ-closure{Î´(q2, 2)}  Â  Â  Â  Â  Â  Â  Â  = {q2}  `

Hence the DFA is

As A = {q0, q1, q2} in which final state q2 lies hence A is final state. B = {q1, q2} in which the state q2 lies hence B is also final state. C = {q2}, the state q2 lies hence C is also a final state.