CODEWITHSUNDEEP
regexbinary
voodoo14
voodoo14

Reputation: 565

Regex for binary multiple of 3

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

Upvotes: 23

Views: 48942

Answers (4)

Marcin
Marcin

Reputation: 36

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

Upvotes: 0

Kert Ojasoo
Kert Ojasoo

Reputation: 711

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.

Upvotes: 71

Casey Chu
Casey Chu

Reputation: 25463

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.

Upvotes: 15

Asmor
Asmor

Reputation: 5181

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)?)+

Upvotes: -2

Related Questions