Regex where all strings containing an even number of 0's:

Question

Question is to construct a regex where all strings containing an even number of 0's: By constructing DFA graphically, it is

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

But it is also

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

Can we prove that they are equal algebraically?

Answer 1

According to the wikipedia page on Kleene Algebra, we can use two properties:

• $(a^*)^*= a^*$
• $(a+b)^* = a^*(b(a^*))^*$

If you allow those it is quite straightforward:

$(1^∗+01^∗0)^∗ = (1^∗)^*\cdot (01^∗0(1^*)^* )^∗ = 1^∗(01^∗01^* )^∗$.

There is probably not a single set of rules for equivalence of regular expressions that everyone egrees on. The rules at wikipedia that I used above are from Dexter Kozen (A completeness Theorem for Kleene Algebras[...], Information and Computation, 1994, open access). The second rule we applied is Proposition 2.7 in that Kozen article. In his notation Kozen uses a partial order $x\leq y$ to represent $x+y= y$. Earlier approaches came from Arto Salomaa (1966) and John Conway (1971). See the History section at wikipedia. I did not study the approaches so I have no comment on this.

Here a (I think) complete set of rules, copied from a presentation of Jacques Sakarovitch. Here that specific rule is called "denesting". It seems an essential rule.

$$ \begin{array}{rc} \text{trivial} & E+0 = 0 + E = E \\ & E\cdot 0 = 0 \cdot E = 0\\ & E\cdot 1 = 1 \cdot E = E \\ \text{associative} & (E_1+E_2)+E_3 = E_1+(E_2+E_3)\\ & (E_1\cdot E_2)\cdot E_3 = E_1\cdot (E_2\cdot E_3) \\ \text{distributive} & E (E_1+E_2) = EE_1+EE_2\\ & (E_1+E_2)E = E_1E+E_2E \\ \text{commutative} & E_1+E_2 = E_2+E_1 \\[0.5ex] \text{unrolling} & E^* = 1 + EE^* = 1 + E^*E \\ \text{denesting} & (E_1+E_2)^* = E_1^* \cdot (E_2\cdot E_1^*)^* \\ \text{sliding} & (E_1\cdot E_2)^*\cdot E_1 = E_1\cdot (E_2\cdot E_1)^* \\[0.5ex] \text{cyclic Zn} & E^* = (1 + E + E^2 + \dots E^{n-1})\cdot (E^n)^* \\[0.5ex] \text{idempotency} & E+E=E\\ & (E^*)^* = E^* \end{array}$$