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?



closed as unclear what you're asking by David Richerby, Juho, Tom van der Zanden, Kyle Jones, cody Nov 20 '17 at 15:06

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

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