Regex for binary multiple of 3

Question

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.

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

Answer 1

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.

Answer 2

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.