in Theory of Computation edited by
6,806 views
32 votes
32 votes

Let $L(R)$ be the language represented by regular expression $R$. Let $L(G)$ be the language generated by a context free grammar $G$. Let $L(M)$ be the language accepted by a Turing machine $M$. Which of the following decision problems are undecidable?

  1. Given a regular expression $R$ and a string $w$, is $w \in L(R)$?
  2. Given a context-free grammar $G$, is $L(G)  = \emptyset$
  3. Given a context-free grammar $G$, is $L(G)  = \Sigma^*$ for some alphabet $\Sigma$?
  4. Given a Turing machine $M$ and a string $w$, is $w \in L(M)$?
  1. I and IV only
  2. II and III only
  3. II, III and IV only
  4. III and IV only
in Theory of Computation edited by
by
6.8k views

1 comment

ans is D as both prob are undecidable.
4
4

3 Answers

31 votes
31 votes
Best answer

$1^{\text{st}}$ statement is Membership problem of regular language $=$ decidable

$2^{\text{nd}}$ statement is Emptyness problem of $CFL =$ decidable

$3^{\text{rd}}$ statement is accept everthing problem of $CFL =$ undecidable

$4^{\text{th}}$ statement is Membership problem of $RE$ language $=$ undecidable

D is answer.

edited by

4 Comments

can you provide any reference
0
0

3rd statement is completeness problem of CFL and CFL is undecidable under completeness problem.

1
1

 , thanks for the name:)

0
0
6 votes
6 votes
Option i and ii are correct.but option iii is false because it is the universality problem which is decidable only for regular languages and DCFL.

Option iv is also undecidable .

And: d) iii and iv only
2 votes
2 votes

answer is D.

turing machine don't have membership algorithm and cfl decidable only for membership,finiteness and emptiness problem.

Answer:

Related questions