6,806 views

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?

1. Given a regular expression $R$ and a string $w$, is $w \in L(R)$?
2. Given a context-free grammar $G$, is $L(G) = \emptyset$
3. Given a context-free grammar $G$, is $L(G) = \Sigma^*$ for some alphabet $\Sigma$?
4. Given a Turing machine $M$ and a string $w$, is $w \in L(M)$?
1. I and IV only
2. II and III only
3. II, III and IV only
4. III and IV only

### 1 comment

ans is D as both prob are undecidable.

$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

can you provide any reference

3rd statement is completeness problem of CFL and CFL is undecidable under completeness problem.

, thanks for the name:)

Option i and ii are correct.but option iii is false because it is the universality problem which is decidable only for regular languages and DCFL.

Option iv is also undecidable .

And: d) iii and iv only
by

turing machine don't have membership algorithm and cfl decidable only for membership,finiteness and emptiness problem.