edited by
8,454 views
32 votes
32 votes

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
edited by

4 Answers

Best answer
63 votes
63 votes
  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$

edited by
10 votes
10 votes

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

edited by
1 votes
1 votes
C Is Correct

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

4th is we Not Say That
Answer:

Related questions