Home > Theory Of Computation > Compound Automata (DFA Example): Construct The Minimum Finite Automata That Accept All The Strings Of a & b Such That String Contains At least 2 a’s & ηb|w|≅0mod3

Compound Automata (DFA Example): Construct The Minimum Finite Automata That Accept All The Strings Of a & b Such That String Contains At least 2 a’s & ηb|w|≅0mod3

Construct The Minimum Finite Automata That Accept All The Strings Of a & b Such That

i) String Contains At least 2 a’s & ηb|w|≅0mod3

Solution:-

(Check Previous Two Problems For Better Understanding)

CONDITION GIVEN:- String Should Contain At least 2 a’s And ηb|w|≅0mod3(Means No Of b’s In String Is Approximately Equal To O Mod 3(If I Divide The No.Of b’s With 3, I Should Get Remainder As 0)

 

FINITE Automata 1:-

Σ={a,b}

L={aa,aaa,aaaa,aaaaa….}

FINITE AUTOMATA 2:-

ηb|w|≅0mod3

Means No Of b’s In String Is Approximately Equal To O Mod 3(If I Divide The No.Of b’s With 3, I Should Get Remainder As 0

Possible Remainders For 3 Are 0,1,2

 

Mean If I Divide No. Of b’s In A String With 3 I Should Get Remainder As 0

 

Imagine-{b,bbb,babbab,bbabbbbba….}

If No Of b’s Are ‘0’ In A String And If I Divide 3 With 0 I’ll Get Remainder ‘0’

 

0 Is Divisible By 3

0 Means ε

Means L={ε,1,2,3}={ε,b,bb,bbbb…}

CROSS PRODUCT

FINITE AUTOMATA 1 × FINITE AUTOMATA 2

=> {(q0,q3),(q0,q4),(q0,q5),

(q1,q3),(q1,q4),(q1,q5),

(q2,q3),(q2,q4),(q2,q5)}

 

FINITE AUTOMATA

FINAL STATE Is q2,q

Because Two Conditions Should Satisfy.

CROSS CHECK

babab // aa,bbb

One thought on “Compound Automata (DFA Example): Construct The Minimum Finite Automata That Accept All The Strings Of a & b Such That String Contains At least 2 a’s & ηb|w|≅0mod3

  1. Nice post. I was checking constantly this blog and I am impressed! Extremely helpful info specially the last part 🙂 I care for such information much. I was seeking this particular info for a long time. Thank you and best of luck.

Leave a Reply