Consider the following problems. 𝐿(𝐺) denotes the language generated by a grammar 𝐺

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 𝐺₁ and 𝐺₂, whether 𝐿(𝐺₁) = 𝐿(𝐺₂)

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