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!
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^nmid ngeq 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^nmid m,ngeq 1}$ is ${0^m1^nmid 1leq mleq n}$, which is non-regular.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/50308 3.2K people like this
