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 𝐺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

We will be happy to hear your thoughts

Leave a reply

Gkseries.com
Logo
Register New Account