0
$\begingroup$

Let L1 be the recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?

a.) L2−L1 is recursively enumerable.

b.)L1−L3is recursively enumerable.

c.)L2∩L3is recursively enumerable.

d.)L2∪L3is recursively enumerable.

My approach:- I am able to falsify a,c and d option. Now for b option i took one example where my L1 is universal language so when i do L1-L3,i get the $L3^c$(L3 complement).So complement of RE but Not REC is NOT RE always.So it is not required that L1-L3 will be RE. But on the other hand if i solve b option as follow:-

L1-L3

= L1 ∩ $(L3)^c$

= REC ∩ $(RE but Not REC)^c$

=REC ∩ NOT RE

So the final expression will give me empty language and it is regular.Is it possible for the final expression to have non empty set above?

|cite|improve this question
$\endgroup$
2
$\begingroup$

The intersection of a recursive language and a non-RE language isn't necessarily empty. Take the recursive langauge to be $\Sigma^*$, as you've already done once.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thank you.I didn't notice that.I was just thinking how can something be both REC and NOT RE. $\endgroup$ – rahul sharma Aug 8 '17 at 0:36
  • 1
    $\begingroup$ A language can't be both recursive and non-RE. But that's not what you're doing here: you're intersecting languages (sets of strings), not language classes. Any particular string could be in a recursive language and in a non-RE one, as you've now realised. $\endgroup$ – David Richerby Aug 8 '17 at 9:38

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.