
Q. Consider the following problems. πΏ(πΊ) denotes the language generated by a grammar πΊ. πΏ(π) denotes the language accepted by a machine π.
I. For an unrestricted grammar πΊ and a string π€, whether π€ β πΏ(πΊ)
II. Given a Turing machine M, whether L(M) is regular
III. Given two grammars πΊ1 and πΊ2, whether πΏ(πΊ1) = πΏ(πΊ2)
IV. Given an NFA N, whether there is a deterministic PDA P such that N and P accept the same language.
Which one of the following statements is correct?
(A) Only I and II are undecidable (B) Only III is undecidable
(C) Only II and IV are undecidable (D) Only I, II and III are undecidable
Ans: Only I, II and III are undecidable