regexdfa

Regular Expression for Binary Numbers Divisible by 3

I am self-studying regular expressions and found an interesting practice problem online that involves writing a regular expression to recognize all binary numbers divisible by 3 (and only such numbers). To be honest, the problem asked to construct a DFA for such a scenario, but I figured that it should be equivalently possible using regular expressions.

I know that there's a little rule in place to figure out if a binary number is divisible by 3: take the number of ones in even places in the digit and subtract by the number of ones in odd places in the digit - if this equals zero, the number is divisible by 3 (example: 110 - 1 in the even 2 slot and a 1 in the odd 1 slot). However, I'm having some trouble adapting this to a regular expression.

The closest I've come is realizing that the number can be 0, so that would be the first state. I also saw that all binary numbers divisible by 3 begin with 1, so that would be the second state, but I'm stuck from there. Could someone help out?

Solution

  • Following what Oli Charlesworth says, you can build DFA for divisibility of base b number by a certain divisor d, where the states in the DFA represent the remainder of the division.

    For your case (base 2 - binary number, divisor d = 310):

    Initial DFA

    Note that the DFA above accepts empty string as a "number" divisible by 3. This can easily be fixed by adding one more intermediate state in front:

    Fixed DFA

    Conversion to theoretical regular expression can be done with the normal process.

    Conversion to practical regex in flavors that supports recursive regex can be done easily, when you have got the DFA. This is shown for the case of (base b = 10, d = 710) in this question from CodeGolf.SE.

    Let me quote the regex in the answer by Lowjacker, written in Ruby regex flavor:

    (?!$)(?>(|(?<B>4\g<A>|5\g<B>|6\g<C>|[07]\g<D>|[18]\g<E>|[29]\g<F>|3\g<G>))(|(?<C>[18]\g<A>|[29]\g<B>|3\g<C>|4\g<D>|5\g<E>|6\g<F>|[07]\g<G>))(|(?<D>5\g<A>|6\g<B>|[07]\g<C>|[18]\g<D>|[29]\g<E>|3\g<F>|4\g<G>))(|(?<E>[29]\g<A>|3\g<B>|4\g<C>|5\g<D>|6\g<E>|[07]\g<F>|[18]\g<G>))(|(?<F>6\g<A>|[07]\g<B>|[18]\g<C>|[29]\g<D>|3\g<E>|4\g<F>|5\g<G>))(|(?<G>3\g<A>|4\g<B>|5\g<C>|6\g<D>|[07]\g<E>|[18]\g<F>|[29]\g<G>)))(?<A>$|[07]\g<A>|[18]\g<B>|[29]\g<C>|3\g<D>|4\g<E>|5\g<F>|6\g<G>)

    Breaking it down, you can see how it is constructed. The atomic grouping (or non-backtracking group, or a group that behaves possessively) is used to make sure only the empty string alternative is matched. This is a trick to emulate (?DEFINE) in Perl. Then the groups A to G correspond to remainder of 0 to 6 when the number is divided by 7.

    (?!$)
(?>
  (|(?<B>4   \g<A>|5   \g<B>|6   \g<C>|[07]\g<D>|[18]\g<E>|[29]\g<F>|3   \g<G>))
  (|(?<C>[18]\g<A>|[29]\g<B>|3   \g<C>|4   \g<D>|5   \g<E>|6   \g<F>|[07]\g<G>))
  (|(?<D>5   \g<A>|6   \g<B>|[07]\g<C>|[18]\g<D>|[29]\g<E>|3   \g<F>|4   \g<G>))
  (|(?<E>[29]\g<A>|3   \g<B>|4   \g<C>|5   \g<D>|6   \g<E>|[07]\g<F>|[18]\g<G>))
  (|(?<F>6   \g<A>|[07]\g<B>|[18]\g<C>|[29]\g<D>|3   \g<E>|4   \g<F>|5   \g<G>))
  (|(?<G>3   \g<A>|4   \g<B>|5   \g<C>|6   \g<D>|[07]\g<E>|[18]\g<F>|[29]\g<G>))
)
(?<A>$|  [07]\g<A>|[18]\g<B>|[29]\g<C>|3   \g<D>|4   \g<E>|5   \g<F>|6   \g<G>)