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

Numbers divisible by three are 0,3,6,9,12…. and their binary representation are 0,11,110,1001,1100,1111…..Check whether these inputs are possible in the given regular expression . In the  option  D , 11100(28) is possible which is not divisible by 3 . Hence we can conclude option D as wrong.

---

From DFA if u delete mod 2 state then mod 3 , you will get options A,C.

if u delete mod 3 state then mod 2 , you will get option B.

Option D generate string 11 11 1 00 which is 124 not divisible by 3 .

---

@Shamshuddin  bro i was confused from your soln so that i am here writing it more clear 

From DFA if u delete mod 2(State labled as $2$ )  then mod 3 (state labeled as $1$)  , you will get options A,C. 

if u delete mod 3 state (State labled as $1$ ) then mod 2 (State labled as $2$ )  , you will get option B.

Option D generate string 111 0  which is 14 not divisible by 3 .

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

yes! kindly match these, these are also being accepted by this DFA.

---

@Arjun sir, Using the DFA, we can directly conclude that A and C are correct Regular Expressions, but how do we verify for B? I tried to take strings of length 1,2 and 3, B seems to generate all of them, but how can we be sure that B is not wrong and will generate all binary strings that are divisible by 3?

---

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

Answer 2

 if you like the soln pls upvote :)

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

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