Let \(L(R)\) be the language represented by regular expression \(R\). Let…

Answer: The undecidable problems are the universality question for a context-free grammar and the acceptance question for a Turing machine (statements III and IV).

• I. Given a regular expression and a string, is the string in the language? — Decidable. Convert the regular expression to an NFA (or directly simulate the expression) and run the automaton on the string; this determines membership effectively.

• II. Given a context-free grammar, is the language empty? — Decidable. Compute the set of generating nonterminals by repeatedly marking any nonterminal that has a production whose right-hand side consists only of terminals and/or already-marked nonterminals. If the start symbol is never marked, the language is empty; otherwise it is nonempty.

• III. Given a context-free grammar, is the language equal to Σ*? — Undecidable. This is the universality problem for context-free grammars, and it is a known undecidable decision problem. There are standard reductions (for example from the Post Correspondence Problem or other classical undecidable problems) showing there is no algorithm that decides for every CFG whether it generates all strings over its alphabet.

• IV. Given a Turing machine and a string, is the string accepted by the machine? — Undecidable. This is the classical acceptance problem for Turing machines (A_TM = {⟨M,w⟩ | M accepts w}) and is known to be undecidable by a standard diagonalization or reduction from the halting problem: if we had a decider for acceptance, we could decide the halting problem, which is impossible.

Therefore the undecidable items are the universality question for CFGs and the membership question for Turing machines; the correct selection is the pair of statements III and IV.