Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

What are the rules of regular expression arithmetics ?

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

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

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

share|cite|improve this question
What exactly is you question? – martini Aug 12 '12 at 8:49
@martini - "What are the rules of regular expression arithmetics ?" in $\mathbb{R}$ for exmaple you have $ab+ac=a(b+c)$ and in the examples I gave there are cirtin rules for regular expression arithmetics as well...I ask about what those rules are (although I do understand that in $\mathbb{R}$ this was an axiom and in our case it can be proven) – Belgi Aug 12 '12 at 8:53
Perhaps look into Kleene algebras. – arjafi Aug 12 '12 at 8:58
What regular expression syntax are you using? In the RE syntaxes I know + is either an ordinary character, or means "one or more times the regular expression preceding it" (i.e. like *, but excluding the empty string). Here, it seems to mean something different (maybe "or")? – celtschk Aug 12 '12 at 9:14
@celtschk: Belgi is clearly using it for OR; I’m more familiar with both $\mid$ and $\lor$ in this context, but I’ve also seen $+$ used. – Brian M. Scott Aug 12 '12 at 9:16
up vote 1 down vote accepted

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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