StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>When you divide a number by three, there are only three possible remainders (0, 1 and 2). What you're aiming at is to ensure the remainder is 0, hence a multiple of three.</p> <p>This can be done by an automaton with the three states:</p> <ul> <li>ST0, multiple of 3 (0, 3, 6, 9, ....).</li> <li>ST1, multiple of 3 plus 1 (1, 4, 7, 10, ...).</li> <li>ST2, multiple of 3 plus 2 (2, 5, 8, 11, ...).</li> </ul> <p>Now think of <em>any</em> non-negative number (that's our domain) and multiply it by two (tack a binary zero on to the end). The transitions for that are:</p> <pre><code>ST0 -> ST0 (3n * 2 = 3 * 2n, still a multiple of three). ST1 -> ST2 ((3n+1) * 2 = 3*2n + 2, a multiple of three, plus 2). ST2 -> ST1 ((3n+2) * 2 = 3*2n + 4 = 3*(2n+1) + 1, a multiple of three, plus 1). </code></pre> <p>Also think of any non-negative number, multiply it by two then <em>add one</em> (tack a binary one on to the end). The transitions for that are:</p> <pre><code>ST0 -> ST1 (3n * 2 + 1 = 3*2n + 1, a multiple of three, plus 1). ST1 -> ST0 ((3n+1) * 2 + 1 = 3*2n + 2 + 1 = 3*(2n+1), a multiple of three). ST2 -> ST2 ((3n+2) * 2 + 1 = 3*2n + 4 + 1 = 3*(2n+1) + 2, a multiple of three, plus 2). </code></pre> <p>This idea is that, at the end, you need to finish up in state ST0. However, given that there can be an arbitrary number of sub-expressions (and sub-sub-expressions), it does not lend itself easily to reduction to a regular expression.</p> <p>What you have to do is allow for any of the transition sequences that can get from ST0 to ST0 then just repeat them:</p> <p>These boil down to the two RE sequences:</p> <pre><code>ST0 --> ST0 : 0+ [0] ST0 --> ST1 (--> ST2 (--> ST2)* --> ST1)* --> ST0: 1(01*0)*1 [1] ([0] ([1] )* [0] )* [1] </code></pre> <p>or the regex:</p> <pre><code>(0+|1(01*0)*1)+ </code></pre> <p>This captures the multiples of three, or at least the first ten that I tested. You can try as many as you like, they'll all work, that's the beauty of mathematical analysis rather than anecdotal evidence.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload