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

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?

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}$$

• I haven't seen Kleene Algebra, is the 2nd equivalence came out sementically or from set of rules? Mar 22 at 7:05
• @steatoda Good question. I added some comments. Mar 22 at 17:43