The Gateway to Computer Science Excellence
0 votes
65 views

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

NOT GETTING THIS QUESTION ANSWER

in Theory of Computation by Loyal (7.8k points) | 65 views

1 Answer

+2 votes
Best answer

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.

by Boss (23.5k points)
selected by
0

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

0
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?
0

@MiNiPanda sorry i think <= 2

AGAIN SILLY MISTAKE

No related questions found

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,394 answers
198,594 comments
105,446 users