favorite Prove or disprove the following implication:
Let R and S be arbitrary regular expressions.
(* - Kleene star) (U - means union)
If R = S* then S(R +S) = S*(R+S)
So, I have figured much this:
If R=S* then:
S(R+S)=L(SR) U L(SS)
=L(SS*) U L(SS)
S*(R+S)=L(S*R) U L(S*S)
=L(S*S*) U L(S*S)
=L(S*) U L(S*S)
So, in the end the implication is equivalent right?
The statement is false. For example, suppose the language of $S$ just accepts the string $\mathtt{1}$. If $R = S^*$, then the language of $R$ consists of 0 or more copies of $\mathtt{1}$.
For the left side of the equation, we know: $$S(R+S) = S(S^*+S) = S(S^*) = SS^*$$
What strings does $SS^*$ accept? It accepts strings that consist of $\mathtt{1}$ followed by zero or more $\mathtt{1}$s. In other words, the language of $S(R+S)$ consists of nonempty strings of $\mathtt{1}$s.
In contrast, $$S^*(R+S) = S^*(S^*+S) = S^*(S^*) = S^*S^* = S^*$$
What strings does $S^*$ accept? It accepts strings that consist of zero or more $\mathtt{1}$s.
The single difference between $SS^*$ and $S^*$ is that $S^*$ accepts the empty string, whereas $SS^*$ does not. Hence when $R=S^*$, the expressions $S(R+S)$ and $S^*(R+S)$ accept slightly different languages.
In manipulating these regular expressions, I'm using the fact that $L+L^* = L^*$ for any language, since $L\subseteq L^*$.