713 views

1 Answer

Best answer
2 votes
2 votes

We need to compute the mod values of 3 depending on the number of occurrences of a and b.

There can be only 3 mod values i.e. 0,1,2. So whatever be the string, after doing the calculation their mod value is going to be among these only. From this we can say that there can be 3 states each representing 1 mod value.

But if mod value is 2 then the state corresponding to that cannot be made the final state. Rest 2 are the final ones.

Initially we are at state q0 with no a's and b's.

The moment we get 1 'a', we do that calculation: (1+2*0)mod3=1 . So send it to state q1.

If we get 'b' at first then (0+2*1)mod3=2 ..send it to q2.

Note that the subscript denotes the mod value of the result.

We follow this process to create the transition table :

 

  a Explanation b Explanation
->q0* q1 If we get string like a. (1+2*0)mod3=1 q2 If we get string like b. (0+2*1)mod3=2
q1* q2

Here see that to come to q1 we have seen 1 a. Now if we see another a (i.e. string aa) then the mod value becomes

(2 + 2*0)mod3=2

q0 Here see that to come to q1 we have seen 1 a. Now if we see b (i.e. string ab) then the mod value becomes (1 + 2*1)mod3=0
q2 q0

Here see that to come to q2 we have seen

1)1 b (From q0). Now if we see an a (i.e. string ba) then the mod value becomes

(1 + 2*1)mod3=0

2)2 a (From q1). Now if we see another a (i.e. string aaa) then the mod value becomes (3 + 2*0)mod3=0

q1

Here see that to come to q2 we have seen

1)1 b (From q0). Now if we see another b (i.e. string bb) then the mod value becomes

(0 + 2*2)mod3=1

2)2 a (From q1). Now if we see b (i.e. string aab) then the mod value becomes

(2 + 2*1)mod3=1

 

There might be other ways to create the table but I follow this one and it gives correct result.

selected by

No related questions found