edited by
8,509 views
33 votes
33 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
edited by

3 Answers

Best answer
32 votes
32 votes

$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
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

77 votes
77 votes
12 answers
2
Arjun asked Feb 14, 2017
28,072 views
Let $\delta$ denote the transition function and $\widehat{\delta}$ denote the extended transition function of the $\epsilon$-NFA whose transition table is given below:$$\...