Let \(L(R)\) be the language represented by regular expression \(R\). Let…

PYQ GATE 2017

Let L(R)L(R) be the language represented by regular expression RR. Let L(G)L(G) be the language generated by a context free grammar GG. Let L(M)L(M) be the language accepted by a Turing machine MM. Which of the following decision problems are undecidable?

I.    Given a regular expression RR and a string ww, is w∈L(R)w \in L(R)?

II.   Given a context-free grammar GG, is L(G)=∅L(G) = \emptyset

III.  Given a context-free grammar GG, is L(G)=Σ∗L(G) = \Sigma^* for some alphabet ΣΣ ?

IV.  Given a Turing machine MM and a string ww, is w∈L(M)w \in L(M)?

  1. A.

    I and IV only

  2. B.

    II and III only

  3. C.

    II, III and IV only

  4. D.

    III and IV only

Attempted by 117 students.

Sign up free to check your answer

Sign up free

Explore the full course: Zero To Hero

Loading lesson…