edited by
16,021 views
58 votes
58 votes

Let $L_1$ be the recursive language. Let $L_2$ and $L_3$ be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?

  1. $L_2 - L_1 \:\text{is recursively enumerable.}$
  2. $L_1 - L_3 \:\text{is recursively enumerable.}$
  3. $L_2 \cap L_3 \:\text{is recursively enumerable.}$
  4. $L_2 \cup L_3 \:\text{is recursively enumerable.}$
edited by

2 Answers

Best answer
88 votes
88 votes

Recursively enumerable languages are closed under union and intersection. So, lets consider each option

  1. $L_2 - L_1 = L_2 \cap \overline{L_1}$
    Recursive languages are closed under complement, and so $\overline{L_1}$ is recursive and hence recursively enumerable also. So, $L_2 \cap \overline{L_1}$ is recursively enumerable is always TRUE.
  2. $L_1 - L_3 = L_1 \cap \overline{L_3}$
    Recursively enumerable languages are not closed under complement. So, $\overline{L_3}$ may or may not be recursively enumerable and hence we can't say anything if $ L_1 \cap \overline{L_3}$ is recursively enumerable or not. 
  3. Intersection of two recursively enumerable languages is always recursively enumerable(RE closed under intersection).
  4. Union of two recursively enumerable languages is always recursively enumerable(RE closed under union).

For verifying closure properties:
http://gatecse.in/wiki/Closure_Property_of_Language_Families

Correct Answer: $B$

edited by
0 votes
0 votes

I hope this makes it simpler!

 

Answer:

Related questions

62 votes
62 votes
9 answers
1
go_editor asked Sep 30, 2014
23,667 views
Let $w$ be any string of length $n$ in $\{0,1\}^*$. Let $L$ be the set of all substrings of $w$. What is the minimum number of states in non-deterministic finite automati...
40 votes
40 votes
1 answer
2
68 votes
68 votes
10 answers
3