1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Erick Wong Nov 10 '13 at 21:33
  • $\begingroup$ 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? $\endgroup$ – TheNotMe Nov 10 '13 at 21:35
  • 1
    $\begingroup$ No, if $L_1=\varnothing$, then $L_1\cup L_2=L_2$. $\endgroup$ – Brian M. Scott Nov 10 '13 at 21:36
  • $\begingroup$ Oh, yes, sorry. $\endgroup$ – TheNotMe Nov 10 '13 at 21:36
  • $\begingroup$ Then my example applies to the $\cdot$ example, sorry, long day of lectures! $\endgroup$ – TheNotMe Nov 10 '13 at 21:37
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.