GATE CS 2017 Set 2 Q.41 (CS Q.41): Decidability, Reducibility and Undecidability

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 \in L(R)$ ?
II. Given a context-free grammar $G$ , is $L(G) = \emptyset$ ?
III. Given a context-free grammar $G$ , is $L(G) = \Sigma^*$ for some alphabet $\Sigma$ ?
IV. Given a Turing machine $M$ and a string $w$ , is $w \in L(M)$ ?

I and IV only

II and III only

II, III and IV only

III and IV only

Official answer and solution

Official answer: D
From: Official GATE 2017 answer key

Solution

Recall standard decidability and undecidability results for regular expressions, context-free grammars, and Turing machines.

Examine each decision problem:

Problem I (Membership for regular expressions): Given $R$ and $w$ , is $w \in L(R)$ ? We can convert $R$ to a DFA and simulate it on $w$ in linear time $O(|w|)$ . This problem is decidable.
Problem II (Emptiness of CFL): Given context-free grammar $G$ , is $L(G) = \emptyset$ ? This can be decided in polynomial time by finding all generating non-terminals and checking if the start symbol $S$ is generating. This problem is decidable.
Problem III (Universality of CFL): Given context-free grammar $G$ , is $L(G) = \Sigma^*$ ? This problem is known to be undecidable (by reduction from the Post Correspondence Problem or computation history of Turing machines).
Problem IV (Membership for Turing machine): Given Turing machine $M$ and string $w$ , is $w \in L(M)$ ? This is the classic Acceptance Problem for Turing Machines ( $A_{\text{TM}}$ ), which is well-known to be undecidable.

Thus, problems III and IV only are undecidable, which corresponds to option D.

Final answer

Common trap

Confusing emptiness of CFL (which is decidable) with universality of CFL (which is undecidable).

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2017 Computer Science and Information Technology (CS) Session 2
Question: 41 of 65, printed as CS Q.41
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source