Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Let $\alpha,\beta \in \text{RA}(\left\{0\right\})$ where $RA(\Sigma)$ is the set of all regular expressions of the alphabet $\Sigma$.

The following two equivalences are given:

  • $\alpha\beta \sim \beta\alpha$
  • $(\alpha + \beta)^* \sim \alpha^* \beta^*$

One of them is wrong, but even after brooding over it I don't find a solution.

The first one should be true because no matter what to show first - the numver of zeros is always the same (x + y zeros = y + x zeros).

I tried to think about the second one less worse in form $$\left[\left[(\alpha + \beta)^*\right]\right] = \left[\left[(\alpha + \beta)\right]\right]^* = \left( \left[\left[\alpha\right]\right] \cup \left[\left[\beta\right]\right] \right)^* = \; ?$$ but as you can see I didn't find any mathematical proof for it (or am just too stupid to see it). Might this be the wrong one? I would have found a counterexample if the language wouldn't contain only $0$'s.

Could you please help me find the solution and identifying my mistakes?

Thanks in advance!

[Edit] We were given the following semantic rules:

semantic rules

share|cite|improve this question
As far as I can figure out, both equivalences are valid when the alphabet contains only one symbol. In fact, the second one follows from the first. What leads you to think that one of them has to be wrong? Also, what is your semantic definition of $L^*$ for $L$ being a set of words? – Henning Makholm Oct 9 '11 at 20:57
@HenningMakholm This task is a preparation for a test. There is no sample solution but only the hint "1 right / 1 wrong". There are no further semantic definitions.. – muffel Oct 9 '11 at 21:13
In that case it seems that the rule $[\![(\alpha^*)]\!] := [\![\alpha]\!]^*$ is meaningless, since the right-hand side doesn't have a definition. – Henning Makholm Oct 9 '11 at 21:19
@HenningMakholm the only related definition is $L^* = \bigcup_{n\geq 0} L^n$, is this what you ment? What did you mean by "The second one follows from the first?" in your first comment? How exactly does the 2nd follow from the first one? – muffel Oct 10 '11 at 14:26
Yes, that's what I meant. I mean that for any reular expressions $\alpha$ and $\beta$ over any alphabet, it holds that if $[\![\alpha\beta]\!]=[\![\beta\alpha]\!]$, then $[\![(\alpha+\beta)^*]\!]=[\![\alpha^*\beta^*]\!]$. You can prove this by assuming that a string is described by one of the sides and prove it is also described by the other side by case analysis on the number of repetitions for each of the relevant $*$'s. – Henning Makholm Oct 10 '11 at 14:51
up vote -1 down vote accepted

Question was answered by Henning Makholm above

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.