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.

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

Posted on  18/10/2020 14:02:19  by  dobsonz
Leave a comment