Consider the following problems. L(饾惡) denotes the language generated by a grammar 饾惡. L(饾憖) 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?

This question was previously asked in

GATE CS 2018 Official Paper

Option 4 : Only I, II and III are undecidable

IBPS SO IT Officer Mains: Full Mock Test

4845

60 Questions
60 Marks
45 Mins

Membership algorithm does not exist for unrestricted grammars.

Regularity problem for TM is undecidable.

Equivalence of Two grammar is undecidable.

Every NFA is a PDA with a finite memory.