edited by
1,055 views
3 votes
3 votes

Let $G_1$ and $G_2$ be arbitrary context free languages and $R$ an arbitrary regular language. Consider the following problems:

  1. Is $L(G_1)=L(G_2)$?
  2. Is $L(G_2) \leq L(G_1)$?
  3. Is $L(G_1)=R$?

Which of the problems are undecidable?

Choose the correct answer from the options given below:

  1. $(i)$ only
  2. $(ii)$ only
  3. $(i)$ and $(ii)$ only
  4. $(i)$, $(ii)$ and $(iii)$
edited by

2 Answers

0 votes
0 votes

Clearly “a” and “b” are undecidable and for “c” it can be reduced to another problem which still be undecidable. Hence option D is correct

Answer:

Related questions