World's most popular travel blog for travel bloggers.

[Solved]: If L1 ∪ L2 and L1 are regular, is L2 also regular?

, , No Comments
Problem Detail: 

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.

Asked By : Victor Brunell

Answered By : Pål GD

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/38008

0 comments:

Post a Comment

Let us know your responses and feedback