-
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 and IV only
- II and III only
- II, III and IV only
- III and IV only
- I and IV only
Correct Option: D
Consider each options :
(a) statement is membership problem of regular language and it is decidable for finite state machine and regular expression.
(b) statement is emptyness problem of CFL emptyness problem is decidable for CFG by checking usefulness of start symbol.
(c) statement is a problem of CFL, and it is undecidable problem, we can not check whether L(G) = ∑* or not but rather we can check complement of L(G) is φ .
(d) statement is a membership problem of a Turing Machine and it is undecidable problem for turning machine. So, options (c) and (d) are undecidable. Hence option (d) is correct.
