Home > Theory Of Computation > Compound Automata (DFA Example): 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

Compound Automata (DFA Example): 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}

  • qIs My Initial And Final State Because Of ε
  • qGoes To qAnd qGoes 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

 

 

One thought on “Compound Automata (DFA Example): 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

  1. Greetings from Carolina! I’m bored to death at work so I decided to browse your website on my iphone during lunch break. I love the knowledge you present here and can’t wait to take a look when I get home. I’m shocked at how quick your blog loaded on my mobile .. I’m not even using WIFI, just 3G .. Anyhow, great site!

Leave a Reply