If $L_1L_2$ is regular language, is $L_2L_1$ regular as well?
I think the answer is no, but I'm not sure how to contradict.
$\begingroup$
$\endgroup$
1
-
2$\begingroup$ Perhaps there's a simple example where $L1$ is a subset of the words of the form $a^n$ and $L2$ is a subset of words of the form $a^nb$. This way the sequences of $a$s get merged in the first case but are separated in the second. $\endgroup$– TomKernDec 18, 2022 at 21:53
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Also following @TomKern suggestion, here is a simpler example on a two-letter alphabet.
Let $L_1 = a^*$ and $L_2 = \{a^{n^2}b \mid n \geqslant 0\}$. Then $L_1L_2 = a^*b$ is regular, but $L_2L_1= \{a^{n^2}ba^m \mid n,m \geqslant 0\}$ is not regular since its intersection with the regular language $a^*b$ is equal to $L_2$, which is not regular.
answered Dec 26, 2022 at 13:44
$\begingroup$
$\endgroup$
Let $L_1 = \{a^ib^j | i \ge j \ge 0\}$ and $L_2 = \{b^k c | k \ge 0\}$.
Now $L_1L_2$ is $\{a^i b^{j+k} c | i \ge j, j \ge 0, k \ge 0\}$, in which there is no relationship between $i$ and $j+k$, so that's equivalent to $\{a^ib^jc | i, j \ge 0\}$, which is the regular language $a^*b^*c$.
But $L_2L_1$ is $\{b^k c a^ib^j | i \ge j \ge 0, k \ge 0\}$ which is not regular (as can easily be seen by intersecting it with $ca^*b^*$).
(Example inspired by a comment from @TomKern.)
