-12
\$\begingroup\$

POSIX version:

^((00)*|(11)*|((10|01)(\2|\3)*(10|01))*)++$

Emacs version:

"\\"^\\(\\(00\\)*\\|\\(11\\)*\\|\\(\\(10\\|01\\)\\(\\2\\|\\3\\)*\\(10\\|01\\)\\)*\\)+"+$"

(in case you were too lazy to add backslashes)

I am absolutely sure that the language of binary strings of arbitrary length with a requirement of even number of ones and zeros is regular (in fact, it is given as an example of deterministic finite automata in the Introduction to Automata Theory, Languages and Computation by Hopcroft and others.

I'm posting this in good faith that my code actually works, but I lack the confidence. Plus, if there is an easier way (the diagram for this DFA is really simple), I'd like to know about it.

\$\endgroup\$

closed as unclear what you're asking by 200_success Sep 1 '15 at 18:03

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • \$\begingroup\$ And what's wrong with ([01][01])+ ? \$\endgroup\$ – rolfl Aug 31 '15 at 15:08
  • \$\begingroup\$ @rolfl this will match 01 - which has odd number of zeros and ones. \$\endgroup\$ – wvxvw Aug 31 '15 at 15:12
  • \$\begingroup\$ @jessehouwing OK, I'll add the start / end requirements, but by matching I didn't mean partial match. So, I don't think this is essential. \$\endgroup\$ – wvxvw Aug 31 '15 at 15:14
  • 1
    \$\begingroup\$ I misunderstood the question, that there have to be an even number of 1's, and an even number of 0's. I just understood the need to be an even number of characters in total. \$\endgroup\$ – rolfl Aug 31 '15 at 15:24
  • 2
    \$\begingroup\$ This question has been mentioned on meta. \$\endgroup\$ – 200_success Sep 1 '15 at 18:18
11
\$\begingroup\$

You expression is almost correct, the use of (\2|\3) will cause issues, as these will match their content, but not their syntax. So certain examples should fail:

011101

Because the 11 can't be substituted by \3, as the capture is empty at that point in time. So you'll have to duplicate the syntax:

^((00)*|(11)*|((10|01)(00|11)*(10|01))*)+$

Then there is some additional optimization you can do. Instead of repeating each internal group 0..* times and the out group 1..* times, you can remove the inner repetition and change the outer one to 0..*:

^(00|11|((10|01)(00|11)*(10|01))*$

Further simplification doesn't seem possible without resorting to tricks such as zero-width assertions, basically ensuring that you end up with an even number of 1's and and even number of 0's and ensuring that both are true:

^(?=0*((10*){2})*$)1*((01*){2})*$

Cheating a bit further, we already know by the capturing expression that we have an even number of 0's, so we can replace the look-ahead to just ensure we're on an even number of characters, there are no other characters to worry about:

^(?=(.{2})*$)1*((01*){2})*$

It's slightly shorter and notice that the first part of the expression is zero-width, the second part is not to ensure that we actually end up with a capture.

The final trick, completely moving away from a DFA, is to use balancing groups, since we're balancing 1's and 0's we know we're even when every odd 1 and 0 has been balanced by its even counterpart. It's not really simpler, but it does work and only needs one pass, like your example:

^((((?<z>0)|(?<o>1))|((?<-z>0)|(?<-o>1))))*(?(z)(?!))(?(o)(?!))$
\$\endgroup\$
10
\$\begingroup\$

There is an algorithm to convert a DFA into a regular expression.

A good explanation is given by in the StackExchange answer: How to convert finite automata to regular expressions?

Here is a demonstration of how it applies to this problem:

We start with this DFA:

enter image description here

and we first remove the OO node yielding:

enter image description here

Next, remove, say, the OE node:

enter image description here

Finally, remove the EO node. The paths from EE to itself are:

r1: 00
r2: 0(11)*0
r3: (0(11)*10 | 1)  (00 | 01(11)*10 )* (1 | 01(11)*0 )
      \_ to EO _/    \_ around EO _/   \_ back to EE _/

The final regex is: (r1 | r2 | r3)*.

\$\endgroup\$
  • 3
    \$\begingroup\$ Unconnected to my original question, might you have references to regular expression optimization techniques? \$\endgroup\$ – wvxvw Aug 31 '15 at 16:54
  • \$\begingroup\$ This book: regex.info/book.html \$\endgroup\$ – jessehouwing Aug 31 '15 at 18:53
  • \$\begingroup\$ Though it really depends on the engine used. \$\endgroup\$ – jessehouwing Aug 31 '15 at 18:54
  • \$\begingroup\$ @jessehouwing I'm not sure if this is something I was after... From reading the preface it seems like it's talking about how to write regular expressions. What I meant is rather given a formal representation of a regular expression find an equivalent regular expression which uses less rules. I.e. optimization as in algorithm for automatic optimization, not for hand-crafting. \$\endgroup\$ – wvxvw Sep 1 '15 at 14:00
8
\$\begingroup\$

This problem is easier to solve with a lookahead combination than with a "match all possibilities" combination. Consider two zero-width lookaheads before the first character. One ensures that each 1 has a following matching 1, and the other ensures that each 0 has a matching 0. if you can guarantee that there are only 1 and 0 characters in the code then you're set.

So, your issue here is that you are trying to count mixed up bit values, but separating them makes the logic much easier:

^(?=(1*01*0)*1*$)(?=(0*10*1)*0*$).*$

Note, there are two lookaheads, and combining them like this essentially makes them two "and" conditions.

The first is:

(?=(1*01*0)*1*$)

That says:

  1. find a 0-bit pair that has some number (perhaps 0) 1 bits before them
  2. allow that pattern to repeat as many times as needed (perhaps 0)
  3. then allow there to be other 1 bits after them to the end of string.

This ensures that there are an even number of 0 values, and all other values are 1's.

The second regular expression is the opposite, it ensures there's an even number of 1 bits, and the other bits are 0.

Combine them together and you can count them easily....

See the pattern working in Java here.

Note that my preference solution would simply be to ensure there are an even number of characters in total (a length % 2 == 0) and then to just ensure an even number of the 0-bits:

^(1*01*0)*1*$

use that as:

return (text.length % 2 == 0) && text.matches("^(1*01*0)*1*$")

That eliminates all the lookaheads and other magic.

\$\endgroup\$
  • \$\begingroup\$ You probably want to replace .* with something else. \$\endgroup\$ – wvxvw Aug 31 '15 at 17:01
  • 1
    \$\begingroup\$ @wvxvw - no, it's fine with it as it is. The lookaheads ensure that there are only 1's and 0's. The .* could be [01]* but that would just make it look more complicated, or would it? \$\endgroup\$ – rolfl Aug 31 '15 at 17:02
  • \$\begingroup\$ Added simplified match using length option, if available. \$\endgroup\$ – rolfl Aug 31 '15 at 17:09
  • \$\begingroup\$ Ah, fair enough, didn't think about it. \$\endgroup\$ – wvxvw Aug 31 '15 at 17:10

Not the answer you're looking for? Browse other questions tagged or ask your own question.