TOC : Conversion of Finite Automata (NDFA) to DFA with Epsilon(ε) | Class-10

For understanding Conversion of Finite Automata (NDFA) to DFA let we first understand FA with ε.

Finite Automata with ε is a set of five tupples ( Q , Σ , δ , q₀ , f )

Where : 

            Q is a set of states.

            Σ is a set of input symbol.

            q₀ is initial state

             f is set of final state.

            δ is transition function of the form.

            δ : ( Q U Σ ) → 2^Q

            δ : Q x ( Σ U ε) → 2^Q                  [ since ε is not a member of Σ)

It as NDFA with ε because it gives many output like  [ q₂ , q₃ ,q_4 ] 

_{CONVERSION OF FINITE AUTOMATA (NDFA) WITH DFA}

_{For this conversion there are two steps :}

_{1. Removal of} ε

2. NFA to DFA conversion.

Let we understand the above steps with the help of example.

QUESTION 1:

Construct a DFA for this Finite Automata (FA)

SOLUTION:

STEP 1 REMOVAL OF ε

On the basis of above transition diagram transition table will be

δ (Transaction Table) =

Construct a Automata on the basis of above transition table:

In this Automata there is no final state so we first find out the final state.

Such as:  q₀ q₁ q₂ ε 

   q₀ ε-closer =[ q₀ q₁ q₂ ]

    here in this set of output there is q₂ so we can say that q₀ is also set to final state.

Same as:

    q₁  ε-closer =[ q₁ q₂ ]

    since   q₁→Final state

    q₂  ε-closer =[ q₂ ]

    since   q₂→Final state

_{The final transition} diagram will be:

_{STEP 2 NFA TO DFA CONVERSION}

NOW From above transition diagram we get:

                 Q  =  [ q₀ q₁ q₂ ]

               2^Q = [ [q₀] , [q₁] , [q₂] , [φ] ,  [ q₁ q₂ ] , ...... ]

               Σ =  [ 0 ,1 ,2 ]

               q₀ = q₀

               f = [ q₀ q₁ q₂ ]

On the basis of above transition diagram δ (Transition Table) =

   here  E means [φ] .

 

QUESTION 2:

Convert into DFA

SOLUTION :

STEP 1 REMOVAL OF ε

Now for conversion first step is to remove ε from above transition diagram

On the basis of above transition diagram the transition table will be :

δ (Transition Table) =

Now find final state.

We know that in above transition diagram q9 is final state  So in above transition table those state which contain q9 are also final state. Such as : q2 , q3 , q4 , q5 , q6 , q8 , q9

STEP 2 NFA TO DFA CONVERSION

Now the transition table is:

δ (Transition Table) =

Consider label for all states such as:

    [A] for [q0]

    [B] for [q2,q3,q4,q6,q9]

    [C] for [q8,q9]

    [D] for [q4,q5,q6,q9]

    [E] for [φ]  ( In above table already change )

Now the new transition table is:

Now the final transition table is:

δ (Transition Table) =

QUESTION 3:

Convert into DFA

SOLUTION :

STEP 1 REMOVAL OF ε

Now transition table of above diagram:

δ (Transition Table) =

Now find final state
Final states will be : [ q0 , q3 , q5 , q6 , q7 ]

STEP 2 NFA TO DFA CONVERSION

Now new transition table after removing ε is :

δ (Transition Table) =

Give some label for all states such as:

[A] = [q0]

[B] = [q1,q2,q3,q4,q6,q7]

[C] = [q1,q2,q4,q5,q6,q7]

Now the transition diagram is:

I hope from the above description and examples we can understand how convert Finite Automata (NDFA) to DFA.