Home > Theory Of Computation > NFA To DFA Conversion In Theory Of Computation

NFA To DFA Conversion In Theory Of Computation

NFA To DFA Conversion In Theory Of Computation

Construct The DFA For The Following NFA

 

 

DFA Using DFA Transition Table

If All States Are Final The Minimal DFA Will Be

My Initial State Will Be My Final State And This Is The DFA.

 

Example-2

Conversion Of NFA To DFA

Find The Minimal No Of States In NFA

Solution:-

Transition Table For Given Diagram

This Is One Of The Different Questions.

To Solve This Question We Are Going To Use Short Cut.

If You Are Expert In Constructing DFA, You Can Solve This Question Using Short Cut.

 

The Question Given Is “Find The Minimal No.Of States In NFA”

Means We Have To Find The Minimum No Of States In Given NFA.

 

There Will Be No Uniqueness In NFA.

If It Is Not Unique, How Can We Find Minimal States?

 

Remember

If The Question Is Asked To Find Minimal No Of States, The Diagram Should Be Unique And Should Be Minimal(Optimized)

We Know DFA Means Minimized, We Can Construct Unique DFA, We Can Construct A Unique DFA For A Language.

It Means The No Of States In DFA wILL Be Unique.

 

“Every DFA Is Not NFA” We Know

But

Every NFA Is Not DFA

 

Simple

We Have To Draw DFA For Given NFA

We Already Drawn Many DFA From NFA’s In Previous Topics.

 

We All Know That Procedure.

 

But Here To Solve This Problem Using Short Cut.

If We Can Predict The Language For Given NFA, Then We Can Find DFA Easily

 

I Have Solved Many Problems Before In Previous Posts

We Have Seen How To Construct DFA Directly In Previous Solved Problems.

 

I Want You To Identify The Language For The Given Nfa & For That NFA For That Language, You Have To Draw DFA.

Very SImple.

If You Observe Above NFA 0,1 Is Going To q0

Then After 3 Zero’s 000, It Is Going To Final State.

Means String Should ContainThree Zero’s(000) Continuously For Sure

And

Final State qHas Loop Of ‘0’, It Means The String Should End With Three Zero’s(000)

String Compulsorily Should Contain 3 Zero’s This Is The Language For This Given NFA.

 

DFA

 

Explanation For DFA

  1. If I Get ‘1’ , I’ll Be On q0 Only
  2. If I Get ‘0 On ‘q0‘ I’ll Go To ‘q1
  3. If I Get ‘0’ On ‘q1‘ I’ll Go To ‘q2
  4. If I Get ‘0’ On ‘q2‘ I’ll Go To ‘q3‘(FINAL STATE)
  5. Because I Should Reach Final State Once I Get 3 Zero’s String
  6. If I ‘1’ On ‘q1‘,’q2‘,’q3‘ I’ll Go To Initial State ‘q0‘ And I’ll Start Machine Again
  7. I Cant Go To Dead State If I Get ‘1’ On q1,q2,q3
  8. If I Go To Dead State I Can’t Get Back And I Cant Start The Machine Again

 

3 thoughts on “NFA To DFA Conversion In Theory Of Computation

Leave a Reply