0
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 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

Reset to default
1
$\begingroup$

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

Improve this answer
$\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.