#FiniteAutomataintheoryofcomputation

[smartcherryposts]

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 q3 Has 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

If I Get '1' , I'll Be On q0 Only If I Get '0 On 'q0' I'll Go To 'q1' If I Get '0' On 'q1' I'll Go To 'q2' If I Get '0' On 'q2' I'll Go To 'q3'(FINAL STATE) Because I Should Reach Final State Once I Get 3 Zero's String If I '1' On 'q1','q2','q3' I'll Go To Initial State 'q0' And I'll Start Machine Again I Cant Go To Dead State If I Get '1' On q1,q2,q3 If I Go To Dead State I Can't Get Back And I Cant Start The Machine Again   Read the full article

[smartcherryposts]

Complement Of Finite Automata

Complement Of Finite Automata Means The Finite Automata Which Is Obtained By Interchanging Final And Non-Final States Is Known As Complement Of Finite Automata.

In This Concept, I'll Change Final States To Non-Final To Final State And Final To Non-Final State. By Doing This The Language Changes. M-Automata(DFA) L-Language M Supports L Language   The String Which Comes In Language L Are Accepted By Machine M L⊆Σ* L Belongs To Sigma Star Σ* Means Universal Set Of Strings(All The Strings) L⊆Σ* Means The Strings Which Are Accepted By Language Comes Under 'L' Not All Strings Comes Under 'L'   M→L⊆Σ* Means Machine M Accepts Strings Which Are Belongs To 'L' And L Is The Language(Set Of Strings) Which Are Subset Of Universal Set Of Strings i.e Σ* (Sigma Star)

Then What Is Complement Of Finite Automata?

If I Give Complement For Machine 'M' That Becomes M1 M1→L1= Σ*- L M1 Is The Machine Which Accepts The Language L1 L1= Σ*- L   This Machine M1 Accepts The Language L1 And L1  Is Universal Set Of Strings Language. M→L⊆Σ* M1→L1= Σ*- L   I Hope You Understood The Difference Between Machine M And Machine M1 Example

Σ={a,b}

L=String Starts With 'a'

This Is (M) Machine Example.  

     2. Σ={a,b}

L=String Does Not Start With 'a'  

This Is M1 (Machine Complement) Example In M1 The Non-Final States Becomes Final State Including Dead State And Final States Becomes Non-Final State.   Cross-Check baa  

Remember

L(FA)∩l(FA1)=Φ L(FA)∪(FA1)=Σ* M→n states k final states M1→ n states n-k final states       Read the full article

[smartcherryposts]

Construct The Minimal Finite Automata That Accept All The String Of a & b Such That There Is Even No. Of a And Even Number Of b

Construct The Minimal Finite Automata That Accept All The String Of a & b Such That i) There Is Even No. Of a And Even Number Of b   Solution:- Question Is Final Automata Should Contain Even Number Of 'a's And Even Number Of 'b's Even Numbers Are 0,2,4,6,8,.....  

CREATE TWO SEPARATE AUTOMATAS WITH GIVEN TWO CONDITIONS

Finite Automata 1:- Even Number Of 'a's Σ={a,b}

q0 Is My Initial And Final State Because Of ε q0 Goes To q1 And q1 Goes To q0(aa) I Dont Bother About Number Of b's On q0q1 Finite Automata 2:- Even Number Of b's(ε,bb,bbbb,bbbbbb....)

I Have Drawn Finite Automata 2 Using The Same Procedure Used In Finite Automata 1.   Now Cross Product (Or) Cross Multiplication Finite Automata 1 × Finite Automata 2

=> {(q0,q2),(q0,q3) (q1,q2),(q1,q3)}  NOS - 4   Now DRAW FINAL DFA Using These States By Observing Finite Automata 1 And Finite Automata 2

Final State Will Be The Combination Of Finite Automata 1 And Finite Automata 2 Only. Because The Condition Given Is Two Conditions Should Be Satisfied. No Of Even 'a's And No. Of Even b's In A String.   Cross Check abaaba

Check Previous Problem For Better Understanding     Read the full article

[smartcherryposts]

Construct Minimal Deterministic Finite Automata (DFA) Start And End With Different Symbol

Construct Minimal Deterministic Finite Automata (DFA) Start And End With Different Symbol Where Σ={a,b}   Condition Given Is If Your String Is Starting With 'a' It Should End With 'b' If Your String Is Starting With 'b' Then It Should End With 'a'   L={ab,ba,abbb,abab,baba,bbaa.........} // Infinite Language

  Read the full article