2
$\begingroup$

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?

$\endgroup$
0

1 Answer 1

3
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.