StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>It turns out that you can do this with a vanilla regular expression. It's just not pretty.</p> <p><code>^((cc|bb)*((bc|cb)(bb|cc)*(bc|cb))*)*(b|c((cc|bb)*((bc|cb)(bb|cc)*(bc|cb))*)*b((cc|bb)*((bc|cb)(bb|cc)*(bc|cb))*)*c)((cc|bb)*((bc|cb)(bb|cc)*(bc|cb))*)*$</code></p> <p>To understand the regular expression, draw a DFA with four states arranged in a square, linked forwards and backwards around the perimeter of the square. The horizontal links represent consuming a B, while the vertical links represent consuming a C. At the top left is the start state, representing having an even number of Cs and an even number of Bs. The top right is the accept state, reached by consuming a B. The bottom states are reached from the top states (and visa-versa) by consuming a C. Now, we can make any number of transitions that preserve the parity of our Cs and Bs, and we'll end up back at the start state. Then we consume a B, bringing us to our accept state. Then from there, so long as we maintain the parities, we're good. Two Cs maintain parity, as do two Bs. That's the <code>(cc|bb)*</code> bit. </p> <p>But you can also maintain parity by going to the opposite corner (via a C and a B in either order), doing as many BB/CC as you like, then returning to the corner you were in (again, either way). That's this bit: <code>((bc|cb)(bb|cc)*(bc|cb))*</code> </p> <p>So, we have <code>((cc|bb)*((bc|cb)(bb|cc)*(bc|cb))*)*</code>, being a set of transitions that gets us back where we started (call it a noop). You can make your odd B transition on either the top, in which case <code>b</code> will do, or the bottom, in which case you need to get down to the bottom with a <code>c</code>, do another noop, then have your <code>b</code>, then another noop, then the <code>c</code> back to the top. </p> <p>I should mention that you can always take two regular expressions and generate a regular expression that matches only strings matched by both of the expressions.</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