Question

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 Turning 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, L (G) = ∅ ?

III. Given a context-free grammar G, is L (G) = ∑* for some alphabet ∑ ?

IV. Given a Turning machine M and a string w, is w L(M)?

Answer 1

(D) III and IV only

L(R) is the language represented by regular expression 

L(G) is the language generated by context free grammar 

L(M) is the language accepted by Turing Machine

I. The problem a given regular expression R and a string w, is w ∈ L(R)? , is a membership problem. Membership problem is decidable for Finite state machine and regular expression.

II. Given Context free grammar G, is L(G) is ϕ? , is emptiness problem for context free grammar. Emptiness problem is decidable for CFG by checking usefulness of start symbol.

III. A given context free grammar G, is L(G) is Σ * for some alphabet Σ?, is undecidable problem. We can’t check whether L(G) = Σ * or not but rather we can check complement of L(G) is ϕ .Since context free language are not closed under complement operation L (G) may be language accepted by Turing Machine and we can’t check emptiness for Turing machine.

IV. Given a Turing Machine M and a string w, is w ∈ L(M)? , is a membership problem for TM. Membership problem is not a decidable problem for TM.