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

137 Views Asked by At

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?

2

There are 2 best solutions below

0
On BEST ANSWER

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.

0
On

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^*$.