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

Question No. 28 CSE | GATE 2015

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. L¯1 (complement of L1) is recursive
II. L¯2 (complement of L2) is recursive
III. L¯1 is context – free
IV. L¯1L2 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.

Comments
UsjiFo http://pills2sale.com/ levitra nizagara

Posted on  18/10/2020 21:11:19  by  dobsonz
EGAmHE http://pills2sale.com/ viagra cialis buy

Posted on  01/11/2020 19:44:28  by  johnanx
J3Ns45 https://www.quora.com/What-the-top-SEO-keywords-for-essay-you-know/answer/Alan-Smith-1772 write my essay

Posted on  04/12/2020 00:28:47  by  dobson
m9KiaC https://www.quora.com/What-the-top-SEO-keywords-for-essay-you-know/answer/Alan-Smith-1772 write my essay

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
pBdPjL https://writemyessayforme.web.fc2.com/octavio-paz-essay-day-of-the-dead.html

Posted on  09/01/2021 08:58:34  by  dobson
KIc8zg https://writemyessayforme.web.fc2.com/octavio-paz-essay-day-of-the-dead.html

Posted on  09/01/2021 12:09:06  by  dobson
trfnup http://waldorfdollshop.us/ waldorf doll

Posted on  09/01/2021 13:12:02  by  johnanz
FPrRSb http://waldorfdollshop.us/ waldorf doll

Posted on  09/01/2021 16:29:17  by  johnanz
Leave a comment