GATE CSE 2021 | Set 2 | Question: 47

Question

Which of the following regular expressions represent(s) the set of all binary numbers that are divisible by three? Assume that the string $\epsilon$ is divisible by three.

• A. $(0+1(01^*0)^*1)^*$
• B. $(0+11+10(1+00)^*01)^*$
• C. $(0^*(1(01^*0)^*1)^*)^*$
• D. $(0+11+11(1+00)^*00)^*$

Comments

https://www.youtube.com/watch?v=MfqQwWvvJPg

---

taking 100 and 101 as they are not accepted helped me eliminate the last option.

rest options are not accepting this

---

Detailed Answer , with intuition behind the dfa construction for it and then deriving options from the dfa:

https://gateoverflow.in/357493/gate-cse-2021-set-2-question-47?show=549396#a549396

Answer 1

The above is the minimal DFA for the given language.

From the given DFA we can see all options except D are correct.

Comments

Option A and C are actually same. We know (a*b*)* = (a+b)*

Now in option C which is ( 0* ( 1(01*0)*1 )* )* , take a=0 ; b=1(01*0)*1

We can easily notice that option C is in (a*b*)* form.

So we can rewrite it as ( 0 + 1(01*0)*1 )* which is same as Option A

---

You can't generate 21(10101) which is divisible
by 3 using options A and C. So only B is correct
Tell me if i am missing something because
everyone is saying A,B,C are correct

---

@Aditya_Pugalia,

Option A and Option C are equivalent. (Try to proove it yourself)

I show how option A is deriving the 21.

21=10101

Option A: ( 0 + 1(01*0)*1 )*

1 -01*0 - 1 = 1-010-1= 10101

Answer 2

 if you like the soln pls upvote :)

Comments

You can't generate 21(10101) which is divisible by 3 using options A and C. So only B is correct

Tell me if i am missing something because everyone is saying A,B,C are correct

---

we can !!

---

nice soln

Answer 3

The catch is that if you use numbers with no asterisk in their powers, you will receive a number that is divisible by three.

Comments

that way option D will also be correct.check it

---

nope, with this method even option D is getting right

Answer 4

After this dfa is constructed, then by state elimination method we will directly get regular expression same as option A →  (0+1(01*0)*1)* and now as per property (a+b)*=(a*b*)* , considering a as 0 and b as 1(01*0)1 we will get option c) (0* (1(01*0)1)*)*  and now for option b and d we will check directly by checking the strings that will be accepted and from that we can observe that 1001(i.e.9) will not be accepted in option d) 

Hence the ans A,B,C

Answer 5

All string Div by 3={epsilon,0,11,110,1001,1100,1111.....}

Option A : it generates all binary string which div by 3 and also generate epsilon.

Option B: it generates all binary string which div by 3 and also generate epsilon.

Option C: Option A and Option C are same.

Option D: Option D is not generate 1001 which is div by 3 then this is wrong.

Answer is Option A,B,C.

Comments

Why do we consider $\epsilon$ as acceptible? I can understand that binary number 0 is divisble by 3 but how can 3 divide an empty binary string?

Answer 6

from the above we can conclude that the strings mentioned in options A,B and C represents the set of all binary numbers divisible by 3.