Q41

MCQ2 marks, −0.67

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 and IV only II and III only II, III and IV only III and IV only

(A)

Given a regular expression $R$ and a string $w$ , is $w \in L(R)$ ?

(B)

Given a context-free grammar $G$ , is $L(G) = \emptyset$

(C)

Given a context-free grammar $G$ , is $L(G) = \Sigma^*$ for some alphabet $\Sigma$ ?

(D)

Given a Turing machine $M$ and a string $w$ , is $w \in L(M)$ ?

Loading…