GATE Computer Science (CS) 2018 Shift 1 Solved Paper

© examsnet.com

Question : 38 of 65

Marks: +1, -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

w

w \in L(G)

II. Given a Turing Machine

M

L(M)

III. Given two grammars

G_{1}

G_{2}

L(G_{1})=L(G_{2})

IV. Given an NFAN, whether there is a deterministic PDA P such that

N

P

accept the same language.

Which one of the following statements is correct?

Only I and II are undecidable
Only III is undecidable
Only II and IV are undecidable
Only I, II and III are undecidable

Go to Question:

Advertisements