Consider the following problems. ๐ฟ(๐บ) denotes the language generated by aโ€ฆ

PYQ GATE 2018

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?

  1. A.

    Only I and II are undecidable

  2. B.

    Only III is undecidable

  3. C.

    Only II and IV are undecidable

  4. D.

    Only I, II and III are undecidable

Attempted by 112 students.

Sign up free to check your answer

Sign up free

Explore the full course: Zero To Hero

Loading lessonโ€ฆ