For this statement state whether it holds for random regular expressions, R,S,A If $RS \equiv AS$, then $R \equiv A$

Question

For this statement state whether it holds for random regular expressions, R,S,A If $RS \equiv AS$, then $R \equiv A$

I made this up wondering if its provable or disprovable.

Answer 1

I am not sure to understand what a random expression is in this context. But, if you choose :

• $S$ the expression denoting the set of words, e.g. $S=(a+b)^*$,
• $A\neq R$ with $\varepsilon\in A\cap R$ ($\varepsilon$ the empty word), e.g. $A=\varepsilon$ and $R=\varepsilon + a$,

$RS\equiv AS\equiv S$ holds but not $R\equiv A$.