GATE CS 2017 (Afternoon) — Question 41

Theory of Computation (TOC)Turing Machines & UndecidabilityMCQ2 marks · −2/3 if wrongMedium

Let L(R) be the language represented by regular expression R. Let L(G) be the language generated by a context free grammar G. Let L(M) be the language accepted by a Turing machine M. Which of the following decision problems are undecidable? I. Given a regular expression R and a string w, is \(w \in L(R)\)? II. Given a context-free grammar G, is \(L(G) = \Phi\)? III. Given a context-free grammar G, is \(L(G) = \Sigma^*\) for some alphabet \(\Sigma\)? IV. Given a Turing machine M and a string w, is \(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
Practise the full 2017-AN paper
Challenge a friend: WhatsApp Telegram
Recommended book · affiliate linkIntroduction to Automata Theory (Hopcroft & Ullman)Regular languages, CFGs, pushdown automata and Turing machines.
Practise more on Turing Machines & UndecidabilityTimed, in the real exam interface · free to start

A GATE question every morning

One real past-paper question every morning for your branch, answer hidden until you tap. Free on Telegram.

Join
Stuck? Ask in the student group