GATE Papers >> CSE >> 2016 >> Question No 27

Question No. 27 CSE | GATE 2016

Which of the following decision problems are undecidable?

I. Given NFAs $N_1$ and $N_2$, is $L$($N_1$)∩$L$($N_2$) =$\mathrm\Phi?$

II. Given a CFG G = $(N,Σ,P,S)$ and a string $x\in\Sigma^\ast$, does $x\in L\ast\left(G\right)?$

III. Given CFGs $G_1$ and $G_2$, is $L$($G_1$) = $L$($G_2$)?

IV. Given a TM $M$, is $L\left(M\right)=\mathrm\Phi?$

Answer : (C) III and IV only

Solution of Question No 27 of GATE 2016 CSE Paper

I.      Disjointedness problem of regular = Decidable

II.     Membership of CFL's = Decidable

III.    Equivalence of CFL's = Undecidable

IV.    Emptiness of RE language's = Undecidable

So, III and IV only is correct answer.

CROlD4 levitra nizagara

Posted on  18/10/2020 14:02:19  by  dobsonz
iMOjpO write my essay

Posted on  04/12/2020 01:09:51  by  dobson
SIOmPt xnxx videos

Posted on  12/12/2020 23:04:48  by  johnan

Posted on  13/12/2020 03:59:03  by  dobson

Posted on  15/12/2020 04:59:33  by  dobson

Posted on  09/01/2021 09:06:08  by  dobson
WEY3gM waldorf doll

Posted on  09/01/2021 13:19:37  by  johnanz

Posted on  17/01/2021 10:27:08  by  johnanz
Leave a comment