SELF DOUBT

Question

https://gateoverflow.in/56617/%23toc-%23peterlinz

NOT GETTING THIS QUESTION ANSWER

Answer 1

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 q₀ 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 q₁.

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

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.

Comments

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

I AM NOT GETTING THIS LINE

---

The language of the Dfa is all those strings where (n(a) + 2*n(b))mod 3<2. So we have to accept all those strings on which after doing this calculation we get 0 or 1 and shouldn't reach final state if we get 2. That is why I said that q0,q1 should be made final states and q2 shouldn't.. is it clear now?

---

@MiNiPanda sorry i think <= 2

AGAIN SILLY MISTAKE