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, 2015 at 16:27
  • 2
    $\begingroup$ Similar question. $\endgroup$
    – Raphael
    Feb 5, 2015 at 16:30
  • $\begingroup$ You tell me. :) $\endgroup$
    – Raphael
    Feb 5, 2015 at 17:36
  • $\begingroup$ possible duplicate of How to prove a language is regular? $\endgroup$
    – D.W.
    Feb 6, 2015 at 0:24

1 Answer 1


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 and acknowledge you have read our privacy policy.

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