# If $L_2L_1$ is accepted by a DFA, is $L_1$ too?

Given that $L_2, L_2L_1$ are accepted by a DFA, is $L_1$ accepted by a DFA too?

What is the general approach to such question? What if instead of $\cdot$ we are given that $L_2 \cup L_1$ is accepted?

• Generally speaking, you should try to think of how you might construct a DFA to recognize $L_1$ given DFAs for $L_2$ and $L_2 L_1$, and if this looks too hard, narrow the source of the difficulty and try to elicit a counterexample that makes it impossible. Play around with simple cases like single-letter alphabets, or cases where $L_2$ is very simple (empty, full), see whether it's true in these restricted domains. – Erick Wong Nov 10 '13 at 21:33
• Then the cup example is false. Because if we take $L_1$ as the empty language, then $L_1 \cup L_2$ is the empty language, both are accepted by a DFA, but if $L_2$ is for example something that isn't accepted, then that just disproves it, yes? – TheNotMe Nov 10 '13 at 21:35
• No, if $L_1=\varnothing$, then $L_1\cup L_2=L_2$. – Brian M. Scott Nov 10 '13 at 21:36
• Oh, yes, sorry. – TheNotMe Nov 10 '13 at 21:36
• Then my example applies to the $\cdot$ example, sorry, long day of lectures! – TheNotMe Nov 10 '13 at 21:37

For the $\cdot$ example, it is obviously wrong. One can take $L_2 = \emptyset$ and $L_1$ as any non-regular language. For the $\cup$ example, it is also wrong. One can take $L_2 = \Sigma^*$ and $L_1$ as any non-regular language.
It is wrong even if you assume that $L_1$, $L_1 \cup L_2$ and $L_1L_2$ are all regular languages, even on a one-letter alphabet $\{a\}$. Take $L_1 = a^*$ and $L_2$ a non regular language containing the empty word. Then $L_1 = L_1 \cup L_2 = L_1L_2 = a^*$.