in Theory of Computation edited by
6,683 views
30 votes
30 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
in Theory of Computation edited by
6.7k views

2 Comments

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

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

4 Answers

61 votes
61 votes
Best answer
  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

4 Comments

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

 

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

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

0
0
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
7 votes
7 votes
C is the answer
by
1 vote
1 vote
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
0
0
Answer:

Related questions