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

Dark Mode

6,683 views

30 votes

Which of the following decision problems are undecidable?

- Given NFAs $N_1$ and $N_2$ , is $L(N_1) \cap L(N_2) = \Phi$
- Given a CFG $G = (N,\Sigma,P,S)$ and a string $x \in \Sigma^{*}$, does $x \in L(G)$} ?
- Given CFGs $G_1$ and $G_2$, is $L (G_1) = L(G_2)$?
- Given a TM $M$, is $L(M)=\Phi$ ?

- I and IV only
- II and III only
- III and IV only
- II and IV only

61 votes

Best answer

- 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.
- Membership in CFG is Decidable (CYK algorithm)
- Equivalence of Two context free grammars is Undecidable.
- For TM M , $L(M) = \phi $ is Undecidable.

Correct Answer: $C$

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

0