Project ForgeLet 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)?
- AI and IV only
- BII and III only
- CII, III and IV only
- III and IV only
Explanation
Regular expression membership (I) is decidable — simulate the equivalent DFA. CFG emptiness (II) is decidable via a standard reachability/derivability algorithm. CFG universality, L(G)=Σ* (III), is a classical UNDECIDABLE problem. Turing machine acceptance, w∈L(M) (IV), is also UNDECIDABLE (it's essentially the halting/acceptance problem). So III and IV are undecidable.
Source: GATE CS 2017 (Session 2) (2017)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.