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?

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.

Answer 2

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

Answer 3

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

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

Answer 4

what about this expression:

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

Answer 5

The most simplified solution I found is:

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

Answer 6

With the fewest symbols,

1*(01*01*)*