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

Prove that $L_1$ is regular if $L_2$, $L_1L_2$, $L_2L_1$ are regular

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

Problem

Prove that $L_1$ is regular if $L_2$, $L_1L_2$, $L_2L_1$ are regular.

These are the things that I would use to start.

  • As $L_1L_2$ is regular, then the homomorphism $h(L_1L_2)$ is regular.



  • Let $h(L_1) = L_2$ and $h(L_2) = L_1$, then $h(L_1L_2) = L_2L_1$ is regular (we already know that) or $h(L_2) = \epsilon$ and we get $L_1$



  • By reflexing, $L_1L_2 = (L_2L_1)^{R}$, same result.



But i don't know how to, for example, intersect something that gives me $L_1$ in order to preserve closure and finally $L_1$ be regular.

Any help?

Solution

Here is a counterexample. Let $L_1$ be any language over some alphabet $\Sigma$ containing the empty string, and let $L_2 = \Sigma^$. Then $L_2 = L_1L_2 = L_2L_1 = \Sigma^$ are all regular, but $L_1$ need not be, in fact it could even be uncomputable!

Context

StackExchange Computer Science Q#11592, answer score: 7

Revisions (0)

No revisions yet.