23

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 :)

Improve this question
3
  • 1
    Does it really have to be a regex? Checking for divisibility would be easier Commented Nov 23, 2015 at 15:08
  • Does it fall in P or NP problem? Commented Jan 31, 2018 at 0: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. Commented Jul 11, 2022 at 18:18

4 Answers 4

Reset to default
71

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

This should be the chosen one
For the "basic regex rules", the reason the initial 0* was removed is explained here: youtu.be/xLp36MhQ_D8?t=411 ... As for where the | 0 came from, it is because (a*b*)* = (a | b)*.
16

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.

Improve this answer

1 Comment

It covers a whole lot more cases though!
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

Improve this answer

3 Comments

Considering, that the string might be long and repeat (check this Kata:codewars.com/kata/54de279df565808f8b00126a/train/java) the complete REGEX should be: ^(1(01*0)*1|0)*$
Please don't add "thank you" as an answer. Instead, vote up the answers that you find helpful. - From Review
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.
-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)?)+
Improve this answer

1 Comment

Actually, I'm wrong. 2 adjacent ones is sufficient, but not necessary, e.g. 9 = 1001. My bad.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.