GATE 2021 CS (CS2) – Question 57
Which regular expressions denote the binary numbers divisible by three? Leading zeros are allowed and ε is treated as divisible by three. Here + means union.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (A) (0+1(01*0)*1)*; (B) (0+11+10(1+00)*01)*; (C) (0*(1(01*0)*1)*)*
Explanation
A comes from eliminating states in the three-state remainder DFA, with transitions r→(2r+b) mod 3. C is a regrouping of the same zero and 1(01*0)*1 blocks. B is another state-elimination form, with zero,11 and 10(1+00)*01 as return-to-zero blocks. D misses the valid word 1001 (nine), which contains neither an initial zero nor an initial 11. Thus A,B,C.