HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
l_1l_2regulartoolanguagethenl_2l_1

Problem

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 too?

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!

Solution

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.

Context

StackExchange Computer Science Q#50308, answer score: 13

Revisions (0)

No revisions yet.