This is a problem in a theory of computation book that's stumping me:
Suppose that we know that L1 ∪ L2 and L1 are regular. Can we conclude that L2 is regular? Explain.
At first, I thought I could build the NFA that is the union of two DFAs, one which accepts L1, and one which we don't know about. Then lambda transition over to the L1 DFA. Then, the union would be regular, but we wouldn't be able to conclude anything about the L2 DFA. I think my reasoning is poor though. Could someone please point me in the right direction? Thank you.
We can't conclude that: Let $L1$ be set of all strings, and let $L2$ be your favorite non-regular language. Then obviously $L1$ and $L1\cup L2=L1$ are regular, but (by our choice) $L2$ isn't.