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)$?

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 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)?

Topic-wise GATE CS PYQs with verified steps