# GATE Papers >> CSE >> 2015 >> Question No 28

Question No. 28

For any two languages L1 and L2 such that L1 is context-free and L2 is recursively enumerable but not recursive, which of the following is/are necessarily true?
I. ${\overline{L}}_{1}$ (complement of L1) is recursive
II. ${\overline{L}}_{2}$ (complement of L2) is recursive
III. ${\overline{L}}_{1}$ is context – free
IV. ${\overline{L}}_{1}\cup {L}_{2}$ is recursively enumerable

##### Answer : (D) I and IV

Solution of Question No 28 of GATE 2015 CSE Paper

L1 is CFL ⇒ ${\overline{\mathrm L}}_1=\overline{\mathrm{CFL}}=\overline{\mathrm{CSL}}=\mathrm{CSL}$

L2 is RE but not REC ⇒ ${\overline{\mathrm L}}_2$ is not RE

Statement 1: ${\overline{\mathrm L}}_1$ recursive is true because compliment of CFL is always a CSL and hence recursive.

Statement 2: ${\overline{\mathrm L}}_2$ is recursive is false because, ${\overline{\mathrm L}}_2$ is not RE.

Statement 3: ${\overline{\mathrm L}}_1$ is CFL is false (${\overline{\mathrm L}}_1$ is need not be CFL).

Statement 4: ${\overline{\mathrm L}}_1\cup{\mathrm L}_2$ is RE is true because, $\overline{\mathrm{CFL}}\cup\mathrm{RE}=\overline{\mathrm{CSL}}\cup\mathrm{RE}=\mathrm{CSL}\cup\mathrm{RE}=\mathrm{RE}\cup\mathrm{RE}=\mathrm{RE}$

So only statements 1 and 4 are true.

UsjiFo http://pills2sale.com/ levitra nizagara

Posted on  18/10/2020 21:11:19  by  dobsonz

Posted on  01/11/2020 19:44:28  by  johnanx

Posted on  04/12/2020 00:28:47  by  dobson

Posted on  04/12/2020 01:00:13  by  dobson
5GDzfv http://xnxx.in.net/ xnxx videos

Posted on  12/12/2020 22:14:04  by  johnan
4g5S8R http://xnxx.in.net/ xnxx videos

Posted on  12/12/2020 23:45:10  by  johnan
hb96fA https://writemyessayforme.web.fc2.com/

Posted on  13/12/2020 04:55:58  by  dobson
FktLb6 https://writemyessayforme.web.fc2.com/

Posted on  13/12/2020 05:29:38  by  dobson
qQYVB3 https://writemyessayforme.web.fc2.com/#writemyessay

Posted on  15/12/2020 05:55:49  by  dobson
18rGRu https://writemyessayforme.web.fc2.com/#writemyessay

Posted on  15/12/2020 06:29:25  by  dobson

Posted on  09/01/2021 08:58:34  by  dobson