# If both the concatenation of two languages and the second “half” are regular, is the first too?

Given that $L_2$ is regular and infinite and $L_1 \cdot L_2$ is regular, then $L_1$ is also regular.

I need some help on getting started on proving this is the case.

My intuition is that if $L_1 \cdot L_2$ is regular there exists a DFA for it, in which case you can just remove the states that correspond to the $L_2$ part of the DFA and you are left with a DFA that recognizes $L_1$.

• 1) Your title did not represent the question at all. 2) You can use LaTeX here. 3) Have you tried applying your idea to a simple example? What do you observe? 4) Are you familiar with the left-/right-quotient of languages? – Raphael Oct 9 '14 at 18:12
• 1) Sorry 2) OK 3) Yes, it wasnt obvious to make 4) I looked up the definitions and understand them – QIANG Oct 9 '14 at 18:16
• for your concrete question, try drawing down the DFA and see what you can find. – xiamx Oct 9 '14 at 18:42
• The problem with your intuition is that you don't know if the DFA can be divided into an L1 part and an L2 part. – reinierpost Oct 10 '14 at 9:26

Suppose that $L_2 = \Sigma^*$ and $L_1$ includes the empty string. Then $L_1 \cdot L_2 = \Sigma^*$, yet $L_1$ doesn't even have to be computable.
• Are you saying that generalized that the first part of a concatenation is always regular if the concatenation is regular? I know examples where $L_{1}$ is non-regular and the concatenation is regular – QIANG Oct 9 '14 at 18:18
• I gave an example in which $L_2$ is regular and infinite, $L_1 \cdot L_2$ is regular, yet $L_1$ is not regular. For concreteness, let $L_1$ consist of the empty string plus all encodings of Turing machines that halt on the empty input. – Yuval Filmus Oct 9 '14 at 18:22
Let $L_1 = a^p$ such that $p$ is prime, let $L_2 = a^*$ then $L_2$ and $L_1 \cdot L_2$ are both regular, but $L_1$ is not