Let $L_1, L_2 \subseteq \Sigma^*$ be two languages, where $\Sigma$ is some finite Alphabet.
Does $L_1L_2 = L_2L_1$ imply $L_1 = L_2$?
What if $L_1$ and $L_2$ are regular languages?
Can you give counterexamples?
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
No, just take as counter example $L_1=\epsilon$ and $L_2$ any other langage different from $L_1$.
$\begingroup$
$\endgroup$
No, counter example: $$ L_1 = a , L_2 = a^* $$
$\begingroup$
$\endgroup$
Hint 1. For words $x_1, x_2 \in \Sigma^*$. If $x_1x_2=x_2x_1$, does this imply that $x_1=x_2$?
Two words commute iff they are powers of a common word. Thus an example would be any pair of languages $L_1,L_2\subseteq\{w\}^*$.
Hint 2. What about $\Sigma = \{a\}$, a one letter alphabet?
Any pair of languages over a single letter alphabet will commute, however complicated.
Hint 3. You may actually find a language $I$ such that $L_1 I = IL_1 = L_1$ for every language $L_1$.
The language $I=\{\varepsilon\}$ is your pal.
answered May 23, 2019 at 16:14