Consider the following problems {L}( {G}) denotes the language generated by a grammar G. L(M) denotes the language accepted by a machine M. I. For an unrestricted grammar {G} and a string {w}, where w ∈ {L}( {G}). II. Given a Turing Machine {M}, whether {L}( {M}) is regular. III. Given two grammars G_{1} and G_{2} whether {L}( {G}_{1})= {L}( {G}_{2}). IV. Given an NFAN, whether there is a deterministic PDA P such that {N} and {P} accept the same language. Which one of the following statements is correct?

Question

Consider the following problems  {L}( {G}) denotes the language generated by a grammar G. L(M) denotes the language accepted by a machine M.   I. For an unrestricted grammar  {G} and a string  {w}, where w ∈  {L}( {G}).   II. Given a Turing Machine  {M}, whether  {L}( {M}) is regular.   III. Given two grammars G_{1} and G_{2} whether  {L}( {G}_{1})= {L}( {G}_{2}).   IV. Given an NFAN, whether there is a deterministic PDA P such that  {N} and  {P} accept the same language.   Which one of the following statements is correct?

Examsnet · Accepted Answer

Correct Answer is : Only I, II and III are undecidable

GATE Computer Science (CS) 2018 Shift 1 Solved Paper