0
$\begingroup$

Suppose I am trying to prove or disprove that:

If $L_1, L_2\in \mathrm{RE}$, then

  • $L_1- L_2 \in\mathrm{RE}$,
  • $L_1 - \overline{L_2}\in \mathrm{RE}$.

Trying to prove those statements, I thought about using the Turing machines $M_1, M_2$ for $L_1, L_2$ respectively, but I can't simulate input on $M_1$ and $M_2$ since they might run forever.

How can I prove (or disprove) those two statements?

$\endgroup$
2
  • $\begingroup$ RE are close under union, intersection, and complement (Hint: OR, AND, and NOT operations on DFAs). Now you can find the solution. $\endgroup$ Commented Apr 20 at 12:09
  • 1
    $\begingroup$ @SubhankarGhosal RE = recursively enumerable, not regular. $\endgroup$ Commented Apr 21 at 7:34

3 Answers 3

1
$\begingroup$

For the statement which is false, you take your easiest example of a non-r.e. language (ie the complement of the Halting problem), and then show how it is expressible in the respective form.

For the statement which is true, you take semidecision procedures for $L_1$, $L_2$ and built one for the relevant language. If you do this properly, then the forever-running is not an issue. Or, if available to you, you invoke the closure of $\mathrm{RE}$ under intersection.

$\endgroup$
0
0
$\begingroup$

We are given $L_1, L_2$ that belong to $RE$, hence there are TMs $M_1, M_2$ that recognize the languages (not decide). To check for $x \in L_1 - L_2$ we need to recognize $x \in L_1$ and $x \notin L_2$. But due to the nature of $RE$ languages, the machine to recognize $x \notin L_2$ may run forever.

Looking at your second problem, we have to recognize $x \notin \bar L_2$, which is same as $x \in L_2$. For a language in $RE$ this is doable. The language $L_1 - \bar L_2$ is the set of strings that belong to $L_1$ but do not belong to $\bar L_2$. The second condition can be written as strings that belong to $L_2$. Using the closure property of $RE$ under intersection you can complete your answer.

$\endgroup$
0
$\begingroup$

You can find in the following link RE that

RE is closed under the Kleene star operations, concatenation, union, and intersection. However, it is not closed under set difference and complementation.

This is because RE's complementation may not be halted. Recursive Languages (R) are the subsets of RE where both the language L and its complements halt, so your statement is true only for R, not for RE in general.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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