3
$\begingroup$

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

  • 0
    @HenningMakholm Ok, thank you!2011-10-10

1 Answers 1

-1

Question was answered by Henning Makholm above