If $L_1L_2$ is regular language then $L_2L_1$ is regular to?

We have two languages: $L_1,L_2$. We know that $L_1L_2$ is regular language, so my question is if $L_2L_1$ is regular to?

I try to find a way to prove it...

I can't assume of course that $L_1,L_2$ are regular...
So I look for a way to prove it.

I'd like to get any hint!

Thank you!

• – Raphael Dec 5 '15 at 21:01

No, $L_2L_1$ is not necessarily regular.

Let $L_1 = \{0,1\}^*$, which is regular, and $L_2 = \{1\} \cup \{0^n1^n\mid n\geq 1\}$, which is not. Then $L_1L_2$ is the set of all strings ending with $1$, which is regular, but $L_2L_1$ is the set of all strings that either begin with $1$, begin with a nonzero number of $0$s followed by at least as many $1$s. This language is not regular, since its intersection with $\{0^m1^n\mid m,n\geq 1\}$ is $\{0^m1^n\mid 1\leq m\leq n\}$, which is non-regular.

• Thank you David, but why is the "$\{1\}\cup \cdots$" at $L_2$? why we need it? Thank you! – stud1 Dec 4 '15 at 17:35
• @stud1 To ensure that $L_1L_2$ is regular. – David Richerby Dec 4 '15 at 17:38
• But $L_1L_2$ (without the $\{1\}$) it's still all the words that ends with $1$, right? So, I still try to understand why we need the $\{1\}$, I hope it's OK I'm asking it :-) Thank you! – stud1 Dec 4 '15 at 19:53
• @stud1 If you delete $\{1\}$ then, for example, $1\notin L_1L_2$. More generally, the only strings that would be in $L_1L_2$ would be the ones ending in $0^mw^n$ for $m\geq n\geq 1$. – David Richerby Dec 4 '15 at 20:55
• @stud1 Correct. – David Richerby Dec 4 '15 at 23:04

I was posting only a hint, then I saw other full answers, so this is a full (hidden) succinct solution :-)

Let $L_1 = \{ 1^p \mid p \text{ is prime}\}$, $L_2 = \{ 1^* 0 \}$; we have $L_1 L_2 = \{ 11^+ 0\}$ which is regular, but $L_2 L_1 = \{ 1^* 0 1^p \mid p \text { is prime}\}$ which is not regular.

• Elegant solution! – Anton Trunov Dec 4 '15 at 17:40
• @AntonTrunov: quite elegant :-) $L_2 = \{1^* 0\}$ can be used to "mask" any non-regular UNARY $L_1$, but as soon as they are swapped $L_1$ is "exposed" again :-) – Vor Dec 4 '15 at 17:43
• What id the meaning of $+$ at $11^+$? – stud1 Dec 4 '15 at 19:55
• @stud1: $1^+$ means "one or more $1s$"; in other words it is a "shortcut" for $\{1^n \mid n \geq 1\}$. So $\{ 11^+0 \} = \{ 110, 1110, 11110, ...\}$ – Vor Dec 5 '15 at 1:30

This is not a hint, but a full answer. Don't read on if you're still trying to solve.

There is no need for $L_2\cdot L_1$ to be regular.

Let $A$ be a unary (non-regular) language such that $A\cdot A$ is regular. Such languages can be found in the post here. Assume $A$ is over the alphabet $\{a\}$.

Define $L_1=\{b\}\cdot A$ and $L_2=A\cdot \{b\}$. Then, you get $L_1\cdot L_2=\{b\}\cdot A^2\cdot \{b\}$, which is regular. However, $L_2\cdot L_1=A\cdot \{bb\}\cdot A$, which can be easily proven to be non-regular, based on $A$ being non-regular.

The following rules define the language associated with any regular expression. Rule 1 The language associated with the regular expression that is just a single letter is that one-letter word alone and the language associated with A is just {A}, a one-word language. Rule 2 If r, is a regular expression associated with the language L, and r 2 is a regular expression associated with the language L2 then,

(i) The regular expression (rl) (r2) is associated with the language L, times L 2. language (r, r2) = L1L 2 (ii) The regular expression r, + r2 is associated with the language formed by the union of the sets L1 and L2. language (rl + r2) = L, + L2 (iii) The language associated with the regular expression (rl)* is LI*, the Kleene closure of the set LI as a set of words. language (rl*) = L1*