26 votes 26 votes 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. $(0+1(01^*0)^*1)^*$ $(0+11+10(1+00)^*01)^*$ $(0^*(1(01^*0)^*1)^*)^*$ $(0+11+11(1+00)^*00)^*$ Theory of Computation gatecse-2021-set2 multiple-selects theory-of-computation regular-expression 2-marks + – Arjun asked Feb 18, 2021 • edited Nov 30, 2022 by Lakshman Bhaiya Arjun 12.3k views answer comment Share Follow See all 6 Comments See all 6 6 Comments reply Show 3 previous comments Manoj D Maiya commented Jun 6, 2023 reply Follow Share 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. 2 votes 2 votes Shamshuddin commented Dec 2, 2023 reply Follow Share 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 . 0 votes 0 votes Ray Tomlinson commented Jan 26 i edited by Ray Tomlinson Jan 26 reply Follow Share @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 . 1 votes 1 votes Please log in or register to add a comment.
Best answer 16 votes 16 votes The above is the minimal DFA for the given language. From the given DFA we can see all options except D are correct. zxy123 answered Feb 18, 2021 • selected Apr 25, 2021 by gatecse zxy123 comment Share Follow See all 9 Comments See all 9 9 Comments reply Show 6 previous comments Harish2426 commented Nov 6, 2021 reply Follow Share yes! kindly match these, these are also being accepted by this DFA. 0 votes 0 votes Tmajestical commented Oct 30, 2022 reply Follow Share @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? 1 votes 1 votes Shukla_ commented Oct 13, 2023 reply Follow Share 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 1 votes 1 votes Please log in or register to add a comment.
16 votes 16 votes if you like the soln pls upvote :) Genius answered Oct 31, 2022 Genius comment Share Follow See all 0 reply Please log in or register to add a comment.
7 votes 7 votes The catch is that if you use numbers with no asterisk in their powers, you will receive a number that is divisible by three. Mohitdas answered Sep 17, 2021 Mohitdas comment Share Follow See 1 comment See all 1 1 comment reply src commented Dec 23, 2023 reply Follow Share that way option D will also be correct.check it 0 votes 0 votes Please log in or register to add a comment.
3 votes 3 votes 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 kathan2021 answered Feb 21, 2022 kathan2021 comment Share Follow See all 0 reply Please log in or register to add a comment.