Igate Test Series

Question

please explain all options with example

Answer 1

Given ,

$L1$ is decidable language/Recursive language

$L2$ is Recursive enumerable language(REL)/Turing recognizable language

Some facts:-

1. Recursive language is also recursive enumerable language.
2. Recursive language is closed under complementation ,intersection ,union ,etc.
3. Recursive enumerable language is closed under union,intersection but not closed under complementation.
4. Complement of recursive enumerable language can be REL or NON REL as well .

Option 1:-

$\bar{L_{1}}\cap \bar{L_{2}}$ =$\bar{\left ( {L_{1}}\cup {L_{2}} \right )}$  [demorgan law]

Now as recursive language is also recursive enumerable language we can consider L1 also as Recursive enumerable language.

Now , $( {L_{1}}\cup {L_{2}})$ is union of two recursive enumerable language which also recursive enumerable .

now complement of ${{L_{1}}\cup {L_{2}}}$ is may be recursive enumerable or may not be as recursive enumerable language is not closed under complementation.

so ,$\bar{L_{1}}\cap \bar{L_{2}}$ is not turing recognizable language.

 

Option 2:-

$L_{1 }\cap L_{2}$ 

$L1$ is recursive language so recursive enumerable language as well.

$L2$ is recursive enumerable language.

So , $L_{1 }\cap L_{2}$ is also recursive enumerable language as recursive enumerable language is closed under complementation.

Now every recursive language is recursive enumerable language but not every recursive enumerable language is recursive .

So, $L_{1 }\cap L_{2}$  is not Turing decidable language.

 

Option 3:-

$\large \frac{L_{1}}{L_{2}}$  (I am considering  the given operation as set difference operator)

=$\large L_{1}-L_{2}$

=$\large L_{1}\cap \bar{L_{2}}$

Now $L_{2}$ is recursive enumerable language , So,it’s complement is not closed as it may or may not be recursive enumerable after complementation.

So $\large L_{1}\cap \bar{L_{2}}$ is not turing decidable language.

Option 4:-

$\large \frac{L_{2}}{L_{1}}$

= $\large L_{2}-L_{1}$

= $\large L_{2}\cap \bar{L_{1}}$

Now $L_{1}$ is recursive language and complement of recursive language is recursive so ,$\bar{L_{1}}$ recursive so as well as recursive enumerable also.

$L_{2}$ is recursive enumerable language.

Now , Recursive enumerable language is closed under intersection So,$\large L_{2}\cap \bar{L_{1}}$ is recursive enumerable.

So,$\large \frac{L_{2}}{L_{1}}$ is turing recognizable language.

Correct answer is (D).

 

 

Comments

why have u considered L1/L2 as a set difference operator ?

---

@shikhar500 i have seen many University paper use this notation to express set difference operation in TOC and as nothing is mentioned in the question so I use set difference operation.

---

Bro here L2 is recursive enumerable only not recursive.

And if language is recursive enumerable but not recursive then compliment of that language is always NON R.E 

 

---

But we are not taking L2 complement in option D.