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

  • 2
    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?2011-10-09
  • 0
    @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..2011-10-09
  • 1
    In that case it seems that the rule $[\![(\alpha^*)]\!] := [\![\alpha]\!]^*$ is meaningless, since the right-hand side doesn't have a definition.2011-10-09
  • 0
    @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?2011-10-10
  • 0
    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.2011-10-10
  • 0
    @HenningMakholm Ok, thank you!2011-10-10

1 Answers 1

-1

Question was answered by Henning Makholm above