This is a problem in a theory of computation book that's stumping me:

Suppose that we know that $L_1 ∪ L_2$ and $L_1$ are regular. Can we conclude that $L_2$ is regular? Explain.

At first, I thought I could build the NFA that is the union of two DFAs, one which accepts $L_1$, and one which we don't know about. Then lambda transition over to the $L_1$ DFA. Then, the union would be regular, but we wouldn't be able to conclude anything about the $L_2$ DFA.

I think my reasoning is poor though. Could someone please point me in the right direction?

Thank you.

  • 2
    $\begingroup$ Hint: make $L_1$ big. Hint 2: make $L_1 \subseteq L_2$. $\endgroup$
    – Raphael
    Feb 5 '15 at 16:27
  • 2
    $\begingroup$ Similar question. $\endgroup$
    – Raphael
    Feb 5 '15 at 16:30
  • $\begingroup$ You tell me. :) $\endgroup$
    – Raphael
    Feb 5 '15 at 17:36
  • $\begingroup$ possible duplicate of How to prove a language is regular? $\endgroup$
    – D.W.
    Feb 6 '15 at 0:24

No, since $\Sigma^* \cup L$ and $\Sigma^*$ are regular languages, for any $L$ and there are non-regular languages, we cannot conclude anything about $L$.


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.