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?

Semiliterate

What programming language uses + for alternatives in regexp? AFAIK, that's only used in automata theory, not when programming. – Haymaker

Why not substr_count()? – Ruhnke

Whoops, may have tagged the wrong thing. Sorry – Semiliterate

homework huh? LOL – Ebersole

I tried this on regexpal.com and it seemed to work: ^(1(11)*|(00)+)$ – Paulita

Any tips?: -- Learn from this answer How to write regular expression for a DFA using Arden theorem Note final state for you is Q3. – Bozcaada

Btw your RE is not correct you are missing many strings – Bozcaada

@Haymaker 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. – Bozcaada

Maybe detect the failure case? (odd number of 0s AND even number of 1s) – Attack

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. – Whiteness

I concur with @Whiteness the base state conditions don't allow for fewer states – Mikemikel

Check my updated answer. 0*1(0|10*1)* is an even shorter regex for the odd-1s part – Attack

@Semiliterate 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"? – Nappy

Answer 1

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

Even-0s part, depends:

1. Empty string is correct: (1|01*0)*
2. No-0s is even-0s: (1|01*0)+
3. 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.

Perce

example of string with odd number of 1s that isn't matched – Whiteness

@Whiteness you're right, had a + instead of a * there, thanks! regexr.com?37nfq – Attack

It doesn't appear to match the empty string (zero 0s is still even). Easy to fix though: changing any or both +s to *. – Commanding

@DPenner yeah, I'm intentionally forcing it to be non-empty – Attack

Well you shaved 4 chars from OPs regex and I think you've taken it as far as it can go ;) +1 – Whiteness

That's what one might think..until someone else comes along :-) – Attack

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 – Bozcaada

@GrijeshChauhan it is correct because it has two zeros. It is even 0s OR odd 1s – Attack

@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. – Attack

Yes correct is (1*01*01*)* + (0*10*10*)*10* + 0*1(0*10*10*)* by mistake I added * at 1 – Bozcaada

@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) – Attack

Yes I checked again and now I think last-two are repentant. We can remove any one. – Bozcaada

Answer 2

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

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

Rhythmical

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. – Attack

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! – Zeeland

and even more importantly...shortest execution time as well! – Disembark

Answer 3

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)*)*$

Disembark

I mean shortest as in fewest symbols. After all, non-capturing groups are just language-dependent sugar. – Attack

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? – Disembark

the bounty is just for fun, to see if there is something shorter – Attack

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? – Disembark

Answer 4

The most simplified solution I found is:

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

Lakieshalakin

Answer 5

With the fewest symbols,

1*(01*01*)*

Whitten

Answer 6

what about this expression:

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

Forjudge