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

GATE · 2017 · CS · Set 2 · Computer Science & IT

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 94 students.

Sign up free to check your answer

Sign up free

Explore the full course: Gate Guidance By Sanchit Sir

Loading lesson…