# Equivalences of regular expressions - which one is wrong?

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.

 We were given the following semantic rules:

-
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