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?


  • $\begingroup$ 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$. $\endgroup$ – quicksort Oct 23 '17 at 21:36
  • $\begingroup$ 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? $\endgroup$ – Megallion Oct 23 '17 at 21:39
  • $\begingroup$ That is indeed another fine counterexample. $\endgroup$ – quicksort Oct 23 '17 at 21:41
  • $\begingroup$ But how do I know if the resulting language is regular or not? $\endgroup$ – Megallion Oct 23 '17 at 21:44
  • $\begingroup$ 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. $\endgroup$ – 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^*$.


Not the answer you're looking for? Browse other questions tagged or ask your own question.