Gate2018 cs Q64

0. 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, whether wϵL(G)
(II) Given a Turing machine M, whether L(M) is regular
(III) Given two grammar G₁ and G₂, whether L(G₁) = L(G₂)
(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 statement is correct?

Answer
Comment
Array

Option : D
Explanation :
Here the match flowing.
I. Membership problem for RE → undecidable
II. Regularity problem for RE → undecidable
III. Equivalence problem for RE → undecidable
IV. Since DPDA P exists for every nfa N and equivalent to it, this problem is trivially decidable.

Forgot your password?

I agree with the Terms.