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

regex regular-language finite-automata
user3085290 picture user3085290 · Dec 10, 2013 · Viewed 29.1k times · Source

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

Julián Urbano picture Julián Urbano · Dec 10, 2013

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.

Related questions

How should one proceed to prove (or find) if two regular expressions are same or equivalent?

For example, in an assignment given to me, we were asked to find out if two regular expressions are equal or not. (a+b+c)* and ((ab)**c*)* My question is how is one supposed to do that? If I …

Read More
Representing identifiers using Regular Expression

The regular definition for recognizing identifiers in C programming language is given by letter -> a|b|...z|A|B|...|Z|_ digit -> 0|1|...|9 identifier -> letter(letter|digit)* This definition will generate identifiers of the form identifier: [_…

Read More
Finding the complement of a DFA?

I am asked to show DFA diagram and RegEx for the complement of the RegEx (00 + 1)*. In the previous problem I had to prove that the complement of a DFA is closed and is a regular expression also, so I know …

Read More