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 One ‘a’ Or One ‘b’

Compound Automata(DFA Example): Construct The Minimal Finite Automata That Accept All The String Of a & b Such That There Is One ‘a’ Or One ‘b’

Construct The Minimal Finite Automata That Accept All The String Of a & b Such That

i) There Is One ‘a’ Or One ‘b’

 

Solution:-

Compound Automata Means Combining Two Automata’s (Machines) Which Becomes One Automata(Machine).

Let’s Know Why We Should Combine Two Automata.

If The Question Contains More Than One Condition ‘ I Have Solved Many Problems In Before Posts ‘.

 

If I Can’t Solve Problems By Considering Two Conditions And I Can’t Create Finite Automata, It Is Little Difficult, I Have To Think More To Solve Problem By Mixing Two Conditions To Create Finite Automata.

That Is Why The Reason Compound Automata Concept Came.

 

In Compound Automata Concept I Have To Merge Two Automata’s.

Then I Have To Create Two Automata’s With Two & Two Conditions.

Then I’ll Merge Both Automata’s Which Becomes Single Automata.

 

So That The Two Conditions Will Be Satisfied.

 

Now Let’s See The Problem Given

Given Σ={a,b}

i) There Is One ‘a’ Or One ‘b’

Means The String Should Contain Either ‘a’ Or ‘b’

 

Conditions

  1. One ‘a’, It Can Be Any Number Of b’s.
  2. One ‘b’, It Can Be Any Number Of a’s.

Means At least One Condition Should Be Satisfied.

It Is Little Difficult To Create DFA Directly.

 

Let’s Create Separate Automata’s For Both The Conditions

Give Different State Names For Two Automata’s, If You Are Solving Compound Automata Problem.

Finite Automata 1:-

One ‘a’, It Can Be Any Number Of b’s

Finite Automata 2:

One ‘b’, It Can Be Any Number Of a’s

 

We Took qAs Initial State Because We Have To Take Different State Names When We Are Solving Compound Automata Problems.

If I Get One ‘b’ I’ll Go To Final State ‘q4

If I Get ‘b’ Again On ‘q4‘ I’ll Go To Dead State ‘q5

 

I Gave ‘q5‘ As Dead State Because We Will Merge Automata 1 And Automata 2 To Get A New Finite Automata If We Give Same State Names For Both Automata 1 And Automata 2, We Can’t Solve Problem Properly.

If I Get a Or b I’ll Be On ‘q5‘ Only.

I’ll Put ‘a’ Self Loop To ‘q3‘ Because I Don’t Have Problem If I Get Any Number Of ‘a’ On ‘q3‘ Because My Condition Is To Get A Single ‘b’, I Don’t Care Any Other, So I’ll Put Self Loop To Other States.

 

qHas ‘a’ Self Loop Similarly

qHas a, b Self Loop Similarly(Which Is A Dead State)

 

At least One ‘a’ Or At least One ‘b’ Automata’s Should Be Combined Now To Get One Single Automata

FA1×FA// Cross Product Of FA1×FA2  

Let’s See How We Will Do Cross Product, If I Do Cross Product Of FA1×FA2  

I’ll Get New States.

 

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

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

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

 

Constructing Finite Automata Using The States Which We Got From Doing Cross Product Of Two Separate Finite Automata’s

 

 

 

Observe FA1& FA

q0,q

Is My Initial State.

 

Observe FA1& FA

If I Give ‘a’ To q& q, I’m Going To q1,q3

If I Give ‘b’ To q& q, I’m Going To q0,q4

 

For First States(q0,q) I Gave a & b

Similarly Now For (q1,q3) I’m Giving ‘a’ & ‘b’

I’ll Get (q2,q3) For ‘a’

I’ll Get (q1,q4) For ‘b’

 

In The Same Way I Gave a & b to (q2,q3)

I’ll Get (q2,q3) For ‘a’

I’ll Get (q2,q4) For ‘b’

 

Upto There I Got  The Primary Diagram

 

No We Will Do Calculations For These States (q0,q4),(q1,q4),(q2,q4)

If I Give a & b To (q0,q4)

I’ll Get (q1,q4) For ‘a’

I’ll Get (q0,q5) for ‘b’

 

If I Give a & b To (q1,q4)

I’ll Get (q2,q4) For ‘a’

I’ll Get (q1,q5) for ‘b’

 

If I Give a & b To (q2,q4)

I’ll Get (q2,q4) For ‘a’

I’ll Get (q2,q5) for ‘b’

 

 

Now Again We Have To See Where a & b’s Of (q0,q5),(q1,q5),(q2,q5) Are Going.

If I Give a & b To (q0,q5)

I’ll Get (q1,q5) for ‘a’

I’ll Get (q0,q5) for ‘b’

 

If I Give a & b To (q1,q5)

I’ll Get (q2,q5) for ‘a’

I’ll Get (q1,q5) for ‘b’

 

If I Give a & b To (q2,q5)

I’ll Get (q2,q5) for ‘a’

I’ll Get (q2,q5) for ‘b’

 

FA Is Ready Now But Which One Is Final State?

Condition Given Is There Is One ‘a’ Or One ‘b’

 

‘Or’ Means Any Of The Condition Is True.The String Will Be Accepted.

My Final States For FA& FAIs q1,q4

 

q1,q

Are My Final States For My Merged FA

 

Wherever You See q& qSeparately Or Combined Those Are Final States For FA.

Cross Check –

abbbb(atleast one ‘a’)

abaa(one ‘a’)

 

How We Solved This Problem

  • Create Two Automata’s For Given Condition
  • By Cross Product We Will Get States
  • Create New FA Using Those States
  • Final States Will Be The Final States We Got In First Two Automata’s

 

 

 

 

 

 

 

 

 

 

One thought on “Compound Automata(DFA Example): Construct The Minimal Finite Automata That Accept All The String Of a & b Such That There Is One ‘a’ Or One ‘b’

Leave a Reply