Shortest regex for binary number with even number of 0s or odd number of 1s

Question

Write an expression that contains an even number of 0s or an odd number of 1s

I got it down to:

1*(01*01*)* + 0*10*(10*10*)*

where the first part represents an even number of 0s and the second part an odd number of 1s

However, there's supposed to be a simplified solution that I'm not seeing. Any tips?

What programming language uses `+` for alternatives in regexp? AFAIK, that's only used in automata theory, not when programming. — Barmar, Dec 10 '13 at 03:31
I tried this on regexpal.com and it seemed to work: `^(1(11)*|(00)+)$` — bdean20, Dec 10 '13 at 05:21
**Any tips?:** -- Learn from this answer [How to write regular expression for a DFA using Arden theorem](http://stackoverflow.com/questions/17420332/need-regular-expression-for-finite-automata/17434694#17434694) Note final state for you is `Q3`. — Grijesh Chauhan, Dec 10 '13 at 10:28
@Barmar In Automata theory `+` as binary operator is Union, and if it appears in supperscript form as unary operator that means repetition for one or more times. — Grijesh Chauhan, Dec 10 '13 at 10:39
Maybe detect the failure case? (odd number of 0s AND even number of 1s) — Julián Urbano, Dec 10 '13 at 15:34
I just wrote a regex from scratch OP and came up with a regex of exactly the same length as yours (and 95% identical). I intentionally didnt read over yours first so I suspect there might not be a shorter expression. — OGHaza, Dec 19 '13 at 18:01
I concur with @OGHaza the base state conditions don't allow for fewer states — gtgaxiola, Dec 19 '13 at 18:21
Check my updated answer. `0*1(0|10*1)*` is an even shorter regex for the odd-1s part — Julián Urbano, Dec 19 '13 at 18:54
@user3085290 Do you want "an even number of 0s _and_ an odd number of 1s" or "an even number of 0s _or_ an odd number of 1s"? — The Guy with The Hat, Dec 21 '13 at 18:32

score 19 · Answer 1 · edited Mar 20 '21 at 07:03

19

Odd-1s part: 0*1(0|10*1)*

Even-0s part, depends:

Empty string is correct: (1|01*0)*
No-0s is even-0s: (1|01*0)+
Must have at least two 0s: 1*(01*01*)+ (as in OP)

old answer: correct under case 1 and 2

(1*(01*0)*)+ | 0*1(0*(10*1)*)*

Kudos to @OGHaza for helpful comments.

edited Mar 20 '21 at 07:03

Wai Ha Lee

8,598
83
57
92

answered Dec 10 '13 at 15:27

Julián Urbano

8,378
1
30
52

[example](http://regexr.com?37nfn) of string with odd number of 1s that isn't matched – OGHaza Dec 19 '13 at 17:38
@OGHaza you're right, had a `+` instead of a `*` there, thanks! http://regexr.com?37nfq – Julián Urbano Dec 19 '13 at 17:46
1

It doesn't appear to match the empty string (zero `0`s is still even). Easy to fix though: changing any or both `+`s to `*`. – DPenner1 Dec 19 '13 at 18:34
@DPenner yeah, I'm intentionally forcing it to be non-empty – Julián Urbano Dec 19 '13 at 18:35
Well you shaved 4 chars from OPs regex and I think you've taken it as far as it can go ;) +1 – OGHaza Dec 19 '13 at 19:18
That's what one might think..until someone else comes along :-) – Julián Urbano Dec 19 '13 at 19:19
Your answer is not correct as it is also possible to generate incorrect string from your RE `(1*(01*0)*)+` use to write `111010` that is incorrect. You may like to check this answer: [Need Regular Expression for Finite Automata: Even number of 1s and Even number of 0s](http://stackoverflow.com/questions/17420332/need-regular-expression-for-finite-automata-even-number-of-1s-and-even-number-o/17434694#17434694) – Grijesh Chauhan Dec 23 '13 at 09:28
@GrijeshChauhan it is correct because it has two zeros. It is even 0s OR odd 1s – Julián Urbano Dec 23 '13 at 10:52
@GrijeshChauhan aren't the 2nd and 3rd parts redundant? Plus, they don't force an odd number of 1s. They force at least one, but there could be any number. – Julián Urbano Dec 23 '13 at 11:37
Yes correct is `(1*01*01*)* + (0*10*10*)*10* + 0*1(0*10*10*)*` by mistake I added `*` at 1 – Grijesh Chauhan Dec 23 '13 at 11:42
@GrijeshChauhan those force at least one 0 (inside parentheses). Again, 2nd and 3rd part are redundant, right? (let's delete old comments so this doesn't grow too long) – Julián Urbano Dec 23 '13 at 11:45
Yes I checked again and now I think last-two are repentant. We can remove any one. – Grijesh Chauhan Dec 23 '13 at 11:52

score 11 · Answer 2 · edited Mar 20 '21 at 07:01

11

Making use of the fact that even-length strings ALWAYS satisfy your constraints:

^(([01]{2})*|1*(01*01*)*)$

edited Mar 20 '21 at 07:01

Wai Ha Lee

8,598
83
57
92

answered Dec 24 '13 at 23:53

Ruud Helderman

10,563
1
26
45

This uses as many symbols as my regex, but I think that very nice catch about even length strings deserves this bounty. Note that this regex requires the no 0s-is-even-0s case. – Julián Urbano Dec 25 '13 at 02:51
1

It would be shorter if `1*(01*01*)*` was replaced by `(1|01*0)*` (as in @JuliánUrbano's solution). But yes, very smart, +1! – Volatility Dec 25 '13 at 03:17
and even more importantly...shortest execution time as well! – gillyspy Dec 28 '13 at 03:25

score 1 · Answer 3 · edited Mar 20 '21 at 07:04

1

Define "shortest". If you're looking for the shortest evaluation time (i.e. fastest) then make sure you do not use capture groups.

here's an example in javascript

^(?:1*(?:01*0)*)+|0*1(?:0*(?:10*1)*)*$

which shows as 20% faster than this expression that uses capture groups but will give you the same answer

^(1*(01*0)*)+|0*1(0*(10*1)*)*$

edited Mar 20 '21 at 07:04

Wai Ha Lee

8,598
83
57
92

answered Dec 24 '13 at 06:45

gillyspy

1,578
8
14

I mean shortest as in fewest symbols. After all, non-capturing groups are just language-dependent sugar. – Julián Urbano Dec 24 '13 at 15:02
yes I think we know what you were going for @JuliánUrbano. So my question is for the op. You're not also the op are you? But for you julian...curious on in what practical scenarios would you (you specifically not the general "you") would prefer the shortest length of expression and not the shortest evaluation time? – gillyspy Dec 24 '13 at 17:45
the bounty is just for fun, to see if there is something shorter – Julián Urbano Dec 24 '13 at 17:47
your comment came in before I saved my question so to clarify: so no practical purpose, just for fun? Also, can we get confirmation that you and the op mean "shorter" in the same way? And who is down-voting me any way, is there some way in which my answer / comments are not relevant given the information we are provided? – gillyspy Dec 24 '13 at 17:50

score 0 · Answer 4 · answered Jan 25 '15 at 06:39

0

The most simplified solution I found is:

1+0(0+1)((1+0)(1+0))*

answered Jan 25 '15 at 06:39

Mehran

308
3
15

score 0 · Answer 5 · edited Mar 20 '21 at 07:00

0

With the fewest symbols,

1*(01*01*)*

edited Mar 20 '21 at 07:00

Wai Ha Lee

8,598
83
57
92

answered Mar 05 '18 at 22:09

Moses Kirathe

322
1
3
14

khalid J-A · Answer 6 · 2021-03-20T06:18:18.673

0

what about this expression:

(1(11)*+(00)*)

edited Mar 20 '21 at 06:18

answered Mar 20 '21 at 06:13

khalid J-A

574
1
7
19

Shortest regex for binary number with even number of 0s or odd number of 1s

6 Answers6