3
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

No, just take as counter example $L_1=\epsilon$ and $L_2$ any other langage different from $L_1$.

$\endgroup$
4
$\begingroup$

No, counter example: $$ L_1 = a , L_2 = a^* $$

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.