1
$\begingroup$

What are the rules of regular expression arithmetics ?

For example: Let $\Sigma=\{0,1\}$

$1. 1+01=(\epsilon+0)1$.

$2. (\epsilon+00)^*=(00)^*$

  • 0
    See [Kleene algebras](https://en.wikipedia.org/wiki/Kleene_algebra).2012-08-12

1 Answers 1

1

Off the top of my head you have at least the following:

  1. $\epsilon\alpha=\alpha=\alpha\epsilon$.
  2. $\alpha+\beta=\beta+\alpha$.
  3. $\alpha+\alpha=\alpha$.
  4. $\alpha\beta+\alpha\gamma=\alpha(\beta+\gamma)$ and $\beta\alpha+\gamma\alpha=(\beta+\gamma)\alpha$.
  5. $(\epsilon+\alpha)^*=\epsilon+\alpha^*=\alpha^*$.
  6. $\epsilon^*=\epsilon$.

If your formalization includes $\varnothing$ (no string) distinct from $\epsilon$ (empty string), you have $\varnothing+\alpha=\alpha$.