GATE Computer Science (CS) 2017 Shift 2 Solved Paper
© examsiri.com
Question : 51 of 65
Marks:
+1,
-0
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 ∈ L(R)?
II. Given a context-free grammar G, is L(G) = Ï•?
III. Given a context-free grammar G, is L(G) = ∑* for some alphabet ∑?
IV. Given a Turing machine M and a string w, is w ∈ L(M)?
I. Given a regular expression R and a string w, is w ∈ L(R)?
II. Given a context-free grammar G, is L(G) = Ï•?
III. Given a context-free grammar G, is L(G) = ∑* for some alphabet ∑?
IV. Given a Turing machine M and a string w, is w ∈ L(M)?
Go to Question: