# If L1 ⊆ L2 and L2 is regular, then L2 − L1 is regular [closed]

I'm having trouble being 100% sure about this answer. I feel like it's false but I'm having trouble coming up with a complete answer. Can someone explain this step by step?

Thanks.

• Are you sure you aren't missing some hypotheses? As it stands it's blatantly false, take e.g. $L_2 = \mathbb{N}$ and $L_1 = K$. – quicksort Oct 23 '17 at 21:36
• Well what if you have L2 = {a*} and L1 = {a^p: p is prime}? L1 is a subset of L2 in this case, but L2 - L1 isn't going to just be a* right? – Megallion Oct 23 '17 at 21:39
• That is indeed another fine counterexample. – quicksort Oct 23 '17 at 21:41
• But how do I know if the resulting language is regular or not? – Megallion Oct 23 '17 at 21:44
• What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving homework-style exercises for you is unlikely to really help you. – David Richerby Oct 24 '17 at 16:41

You can show that if $L_1 \subseteq L_2$ and $L_2$ is regular, then $L_2 \setminus L_1$ is regular iff $L_1$ is regular. This follows from the product construction, for example. Taking $L_2 = \Sigma^*$, we find that $\Sigma^* \setminus L_1$ is regular iff $L_1$ is regular. Hence if $L_1$ is any non-regular language, then it refutes your statement taken with $L_2 = \Sigma^*$.