3
$\begingroup$

If $L_1$ and $L_2$ are both non-decidable languages (Not decidable, so can be SD or $\lnot$SD), is it possible that $L_1-L_2$ is regular and $L_1-L_2\neq\phi$, where $\phi$ is the empty set?

What's a good way of tackling this question? Me and some classmates have been stuck on this question for a while, and this was the best we've got:

It should be possible given the following example:

Let $L_1=H\cup a^*$ and $L_2=H$, where $H=\{<M,w>:$ Turing machine $M$ halts on $w$$\}$, so $L_1-L_2=L_1\cap \lnot L_2=(H\cup a^*)\cap \lnot H=\lnot H\cap a^* = a^*$ which is regular. (we are saying $H$ does not contain $a^*$, so $\lnot H$ must contain $a^*$, hence why the intersection gives $a^*$.)

But we are not confident this is correct due to the last part with the intersection does not feel right. What's the answer to this question?

$\endgroup$
3
$\begingroup$

Your example almost works. You need to make sure that the regular part is disjoint from the non-decidable part.

Suppose our alphabet has at least two symbols, say $a$ and $b$. Consider any undecidable langauge $H$, for example the halting set, and define $$L_2 = \lbrace b w \mid w \in H\rbrace$$ and $$L_1 = L_2 \cup \lbrace a \rbrace.$$ Now it is obvious that $a \not\in L_2$ because all words in $L_2$ start with $b$. Also, $L_2$ and $L_1$ are undecidable because there are easy reductions from $H$ to them, and back. And of course we have $$L_1 \setminus L_2 = \{a\},$$ which is decidable. You can make the example more complicated by taking any decidable langauge $D$ and define $L_2$ as before, but change $L_1$ to $$L_1 = L_2 \cup \{a w \mid w \in D\}.$$ This way $L_1 \setminus L_2$ is computably isomorphic to $D$.

$\endgroup$
  • $\begingroup$ Thank you so much for the reply and your detailed explaination! :) $\endgroup$ – Pengibaby Nov 21 at 19:51
2
$\begingroup$

As you suspected, it can happen that $L_1-L_2\not=a^*$. The assumption that $H$ does not contain $a^*$ does not imply that $\lnot H$ must contain $a^*$. For example, if $H\cap a^*= \{a^2\}$, then $\lnot H$ does not contain $a^2$, let alone $a^*$.

The technique to arrive at a simple solution is to let the regular part be disjoint with $L_2$.

Here is the simplest way to find $L_2$ so that $L_1-L_2$ is undecidable, given any undecidable language $L_1$. Since $L_1$ is undecidable, it must contain at least one word. Let $w\in L_1$. Let $L_2$ be $L_1$ without $w$. Then $L_1-L_2=\{w\}$ is regular. You can check that $L_2$ is undecidable.


Exercise 1. (easy) Given an undecidable language $L_2$, find an undecidable language $L_1$ such that $L_1-L_2$ is regular.

Exercise 2. (easy) Give an example where the subtraction between two non-context-free languages is regular.

Exercise 3. (one or several minutes) Give any regular language $R$, find an example such that the subtraction between two undecidable languages is $R$.

$\endgroup$
  • $\begingroup$ Thank you for your response and clearing things up :) $\endgroup$ – Pengibaby Nov 21 at 20:19
2
$\begingroup$

Just take for $L_2$ an undecidable language of $a^*$ and take $L_1 = L_2 \cup \{b\}$. Then $L_2$ is also undecidable and $L_2 - L_1 = \{b\}$ is regular.

$\endgroup$
  • $\begingroup$ Thank you for your help! I really appreciate it :) $\endgroup$ – Pengibaby Nov 21 at 20:20
  • $\begingroup$ You're welcome. $\endgroup$ – J.-E. Pin Nov 21 at 20:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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