Dark Mode

6,806 views

32 votes

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?

- Given a regular expression $R$ and a string $w$, is $w \in L(R)$?
- Given a context-free grammar $G$, is $L(G) = \emptyset$
- Given a context-free grammar $G$, is $L(G) = \Sigma^*$ for some alphabet $\Sigma$?
- 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

31 votes

Best answer

$1^{\text{st}}$ statement is Membership problem of regular language $=$ **decidable**

$2^{\text{nd}}$ statement is Emptyness problem of $CFL =$ **decidable**

$3^{\text{rd}}$ statement is accept everthing problem of $CFL =$ **undecidable**

$4^{\text{th}}$ statement is Membership problem of $RE$ language $=$** undecidable**

**D is answer.**