6,683 views

Which of the following decision problems are undecidable?

1. Given NFAs $N_1$ and $N_2$ , is $L(N_1) \cap L(N_2) = \Phi$
2. Given a CFG $G = (N,\Sigma,P,S)$ and a string  $x \in \Sigma^{*}$, does  $x \in L(G)$} ?
3. Given CFGs  $G_1$ and $G_2$, is $L (G_1) = L(G_2)$?
4. Given a TM $M$, is $L(M)=\Phi$ ?
1. I and IV only
2. II and III only
3. III and IV only
4. II and IV only

I am confused on equivalence of cfg. We can draw two pda and compare the pda right?
can anyone explain option IV ??

does it mean - Language accepted by TM M doesnt accept anything i,e Φ ???

1. is Decidable, we may use cross product of NFA (or by converting them into DFA) , if We didn't get final states of both together at any state in it. then $L(N_1)\cap L(N_2)= \phi$ , Disjoint languages.
2. Membership in CFG is Decidable (CYK algorithm)
3. Equivalence of Two context free grammars is Undecidable.
4. For TM M , $L(M) = \phi$ is Undecidable.

Correct Answer: $C$

Sir I didn't get the 1st part soln plz elaborate y it is so ?

Thanks
in this question in option 3 are we talking about CFL or DCFL?????

@Ankit Meena We are talking about language produced by CFG, by default CFL (because DCFL is also CFL). For CFL, equivalence is undecidable.

Option C will be right option

Explanation::
Since equality problem is always undecidable in the case of CFL,CSL,RL and RE.

Similarly Emptiness proble is Undecidable in the case of TM,CSL,RL

by
C Is Correct

2nd is Basic Rule We Can not  Compare two CFG are Equal or Not

4th is we Not Say That

### 1 comment

4th one is emptiness problem of turing machine which is undecidable