20

I would like to know how can I construct a regex to know if a number in base 2 (binary) is multiple of 3. I had read in this thread Check if a number is divisible by 3 but they dont do it with a regex, and the graph someone drew is wrong(because it doesn't accept even numbers). I have tried with: ((1+)(0*)(1+))(0) but it doesn't works for some values. Hope you can help me.

UPDATE: Ok, thanks all for your help, now I know how to draw the NFA, here I left the graph and the regular expresion:

In the graph, the states are the number in base 10 mod 3.

For example: to go to state 1 you have to have 1, then you can add 1 or 0, if you add 1, you would have 11(3 in base 10), and this number mod 3 is 0 then you draw the arc to the state 0.

Whiteboard version

((0*)((11)*)((1((00) *)1) *)(101 *(0|((00) *1 *) *0)1) *(1(000)+1*01)*) *

And the other regex works, but this is shorter.

Thanks a lot :)

Community
  • 1
  • 1
voodoo14
  • 515
  • 2
  • 6
  • 10
  • 1
    Does it really have to be a regex? Checking for divisibility would be easier – Zorgatone Nov 23 '15 at 15:08
  • Does it fall in P or NP problem? –  Jan 31 '18 at 00:31
  • To check if a binary number is divisible by 3, count the number of non-zero odd positions bits and non-zero even position bits from the right. If their difference is divisible by 3, then the number is divisible by 3. – hb20007 Jul 11 '22 at 18:18

4 Answers4

67

I know this is an old question, but an efficient answer is yet to be given and this question pops up first for "binary divisible by 3 regex" on Google.

Based on the DFA proposed by the author, a ridiculously short regex can be generated by simplifying the routes a binary string can take through the DFA.

The simplest one, using only state A, is:

0*

Including state B:

0*(11)*0*

Including state C:

0*(1(01*0)*1)*0*

And include the fact that after going back to state A, the whole process can be started again.

0*((1(01*0)*1)*0*)*

Using some basic regex rules, this simplifies to

(1(01*0)*1|0)*

Have a nice day.

Kert Ojasoo
  • 671
  • 1
  • 5
  • 3
  • 1
    This should be the chosen one – Gayan Weerakutti Oct 11 '18 at 07:22
  • For the "basic regex rules", the reason the initial `0*` was removed is explained here: https://youtu.be/xLp36MhQ_D8?t=411 ... As for where the `| 0` came from, it is because `(a*b*)* = (a | b)*`. – hb20007 Jul 11 '22 at 18:15
15

If I may plug my solution for this code golf question! It's a piece of JavaScript that generates regexes (probably inefficiently, but does the job) for divisibility for each base.

This is what it generates for divisibility by 3 in base 2:

/^((((0+)?1)(10*1)*0)(0(10*1)*0|1)*(0(10*1)*(1(0+)?))|(((0+)?1)(10*1)*(1(0+)?)|(0(0+)?)))$/

Edit: comparing to Asmor's, probably very inefficient :)

Edit 2: Also, this is a duplicate of this question.

Community
  • 1
  • 1
Casey Chu
  • 25,069
  • 10
  • 40
  • 59
0

For some who is learning and searching how to do this:

  1. see this video: https://www.youtube.com/watch?v=SmT1DXLl3f4&t=138s

  2. write state quations and solve them with Axden's Theorem

  3. The way I did is visible in the image-result is the same as pointed out by user @Kert Ojasoo. I hope i did it corretly because i spent 2 days to solve it...

  4. Solution

Marcin
  • 36
  • 5
  • Considering, that the string might be long and repeat (check this Kata:https://www.codewars.com/kata/54de279df565808f8b00126a/train/java) the complete REGEX should be: ^(1(01*0)*1|0)*$ – Marcin Jan 16 '22 at 20:48
  • Please don't add "thank you" as an answer. Instead, vote up the answers that you find helpful. - [From Review](/review/late-answers/30830957) – buddemat Jan 19 '22 at 19:49
  • Your answer does not add anything to the existing one from @KertOjasoo, as you write yourself. Please do not add answers that essentially already exist. – buddemat Jan 19 '22 at 19:51
-2

n+2n = 3n. Thus, 2 adjacent bits set to 1 denote a multiple of 3. If there are an odd number of adjacent 1s, that would not be 3.

So I'd propose this regex:

(0*(11)?)+
Asmor
  • 5,043
  • 6
  • 32
  • 42
  • 3
    Actually, I'm wrong. 2 adjacent ones is sufficient, but not necessary, e.g. 9 = 1001. My bad. – Asmor Nov 02 '11 at 01:01