Question

For any two language $L_{1}and{L}_2$ such that $L_1$ is context free and $L_2$ is recursively enumerable but not recursive, which of the following is/are necessarily true?
1. $\overline{L_1}$ (complement of $L_1$) is recursive
2. $\overline{L_2}$ (complement of $L_2$) is recursive
3. $\overline{L_1}$ is context-free
4. $\overline{L_1}\cup L_2$ is recursively enumerable

• A. 1 only
• B. 1 and 4 only
• C. 3 only
• D. 3 and 4 only

Answer 1

The correct option is B 1 and 4 only

$L_1$ is CFL $\Rightarrow \overline{L_1}=\overline{CFL}=\overline{CSL}=CSL$
$L_2$ is RE but not REC $\Rightarrow \overline{L_2}$ is not RE
Statement 1: $\overline{L_1}$ is recursive is true because, compliment of CFL is always a CSL and hence recursive.
Statement 2: $\overline{L_2}$ is recursive is false because, $\overline{L_2}$ is not RE.
Statement 3: $\overline{L_1}$is CFL is false $(L_1$ is need not be CFL)
Statement 4: $\overline{L_1}\cup L_2$ is RE is true because, $\overline{CFL}\cup RE=\overline{CSL}\cup RE=CSL\cup RE=RE\cup RE=RE$
So only statements 1 and 4 are true