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
