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 Turing machine M.
Which of the following decision problems are undecidable?
I. Given a regular expression R and a string w,is $\omega \epsilon$L(R)?
II. Given a context-free grammar G, is L(G)=$\varphi$
III. Given a context-free grammar G, is L(G) = ${\sum }^{\ast }$ for some alphabet $\sum$?
IV. Given a Turing machine M and a string $\omega$, is $\omega \epsilon$L(M)?

Answer 1

I. Membership of regular language (Decidable)
II. Emptiness of CFL (Decidable)
III. L=${\sum }^{\ast }$ problem of CFL (Undecidable)
IV. Membership of RE language (Undecidable)
So, only III and IV are undecidable.
So, correct answer is (d).