4,121 views

Which of the following statements is/are $\text{TRUE}?$

1. Every subset of a recursively enumerable language is recursive.
2. If a language $\textit{L}$ and its complement $\overline{\textit{L}}$ are both recursively enumerable, then $\textit{L}$ must be recursive.
3. Complement of a context-free language must be recursive.
4. If $\textit{L}_{1}$ and $\textit{L}_{2}$ are regular, then $\textit{L}_{1} \cap \textit{L}_{2}$ must be deterministic context-free.

Option A :

“Every subset of a recursively enumerable language is recursive.” : False.

We know that Every language is a subset of $\Sigma^*,$ and $\Sigma^*$ is a recursively enumerable language. (Every regular language is a recursively enumerable language)

Now, consider any Non-recursive language $L.$ $L$ is subset of $\Sigma^*,$ but $L$ is Non-recursive language, So, we can say that the statement  “Every subset of a recursively enumerable language is recursive.” is False.

NOTE that : “Set of all recusrive languages” is proper subset of “Set of all recursively enumerable languages”. BUT a particular recursive language Need not be subset of a particular recursively enumerable language.

For example, consider the language $L$ below :

$L = \{ <M> | M \text{ is a Turing machine, } L(M) \text{ is empty} \}$

We know, by Rice Theorem, that $L$ is undecidable, and unrecognizable. i.e. $L$ is Non-recursive as well as Non-RE language.

But $L$ is subset of $\Sigma^*.$

We can prove that “Every infinite language L has a subset S which is undecidable.

In fact, both the following statements are true :

1. Every infinite language L has a subset S which is undecidable.
2. Every infinite language L has a subset S which is unrecognizable.

Refer my answer here for proof of these statements : https://gateoverflow.in/357504/Gate-cse-2021-set-2-question-36?state=edit-357698

https://cs.stackexchange.com/questions/102585/is-every-subset-of-a-re-language-also-re-in-general

Option B :

“If a language $L$ and its complement $\overline{L}$ are both recursively enumerable, then $L$ must be recursive.” : True.

Proof :

Let $L$ be a recursively enumerable language such that $\overline{L}$ is also recursively enumerable. By definition of recursively enumerable language, $L$ is accepted by some Turing machine $M_1$, and $\overline{L}$ is accepted by some Turing machine $M_2.$

Note that if a language $S$ is accepted by a Turing machine $N$ then $N$ definitely halts on all the strings in $S.$

Now, consider language $L.$ Take any string $w \in \Sigma^*,$ run $w$ on $M_1,M_2$ in parallel(Or in interleaved fashion), at least one of $M_1$ or $M_2$ will definitely halt on $w.$

If $w \in L$ then $M_1$ will definitely halt on $w.$

If $w \notin L$ then $w \in \overline{L}$, So, $M_2$ will halt on $w.$

So, for any string $w \in \Sigma^*,$ at least one of $M_1$ or $M_2$ will definitely halt, hence, for every string, we can decide whether $w$ belongs to $L$ or $w$ belongs to $\overline{L}.$

Hence, $L$ is recursive.

Complements of Recursive and Recursively Enumerable Languages :

• A recursive language is one that is accepted by a TM that halts on all inputs.
• The complement of a recursive language is recursive.
• If a language L and its complement are RE, then L is recursive.
• A language can be RE but its complement need not be RE.

https://math.stackexchange.com/questions/3624962/is-a-language-l-recursive-if-it-and-its-complement-lc-are-both-recursively

http://www.cs.columbia.edu/~aho/cs3261/Lectures/L15-Diagonalization_Language.html

Option C :

“Complement of a context-free language must be recursive.” : True.

Complement of a context-free language may or maynot be CFL but since every CFL is CSL, and complement of CSL is always CSL.

So, Complement of a context-free language must be CSL, hence, must be recursive.

Option D :

“If $L_1$ and $L_2$ are regular, then $L_1 \cap L_2$ must be deterministic context-free.” : True.

Intersection of two regular languages is a regular language. If $L_1$ and $L_2$ are regular, then $L_1 \cap L_2$ is regular, hence, is deterministic context-free.

If a language and its complement is Recursively enumerable Then L is Recursive .It is the standard result And proof is also very easy.

So option B is true.

Complement of CFL must be Recursive. It is also True.

As we know the complement of CFL may or may not be CFL but it is bound to be Context sensitive language which means it is recursive As well.

So option C is also True.

Option D,

L1 and L2 both are Regular languages, so their intersection is also regular as regular language is closed under intersection.

Now Regular language is also deterministic context free language

so option D is also true.

Option A ,

every subset of recursive enumerable language is Recursive.

This statement is false.

Counter example ,

Say Sigma* is set of all strings  which is an RE language.

Now every language is subset of sigma*.

Now any Recursively enumerable language is also subset of sigma* which is not recursive.

So option A is false.

https://cs.stackexchange.com/questions/102585/is-every-subset-of-a-re-language-also-re-in-general