[Solved]: If $L_1L_2$ is regular language then $L_2L_1$ is regular to?

Problem Detail: 

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!

Asked By : stud1

Answered By : David Richerby

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/50308

3.2K people like this

 Download Related Notes/Documents