edited by
15,544 views
43 votes
43 votes

Which of the following problems are decidable?

  1. Does a given program ever produce an output?
  2. If $L$ is a context-free language, then, is $\bar{L}$ also context-free?
  3. If $L$ is a regular language, then, is $\bar{L}$ also regular?
  4. If $L$ is a recursive language, then, is $\bar{L}$ also recursive?
  1. $1, 2, 3, 4$
  2. $1, 2$
  3. $2, 3, 4$
  4. $3, 4$
edited by

7 Answers

2 votes
2 votes
1. L is set of all program. for some of the input TM say yes i accept it and for some of the input TM can say no  it means we can divide input into two part i.e. yes or no

so any program ever produce an o/p or not produce output is non trivial property. So according to Rice theoram it is Undecidable..

2. membership .emptyness, finiteness is decidable in CFL and rest are undecidable so compliment is undecidable . and you can also prove it i.e

L is set of all CFL. For this language whether any member's complement is CFL or not is non trivial property. because CFL are not closed under complement. so complement of CFL can be CFL or can not be CFL. So According to Rice theorem it is Undecidable.

3. L is set of all RL. For this language whether any member's complement is RL or not RL is trivial property. because RL are  closed under complement that is  complement of RL is RL . So According to Rice theorem it is Decidable.

4. L is set of all Recursive languages. For this language whether any member's complement is Recursive languages or not is trivial property. As Recursive languages are  closed under complement. So According to Rice theorem it is Decidable.
edited by
0 votes
0 votes

FOR OPTION 1) Explaination is if a program is given then it is made from logic and we know that the limitation of logic is TM(turing machine) so it may be possible that TM produce output or it may be hang(means doesnot produce output) hence option 1 is undecidiable…..

FOR OPTION 2) Explaination is context free language is decidiable in M,E,FINITE(membership, empiteness and finiteness) but it is asking about complement hence it is not decidiable…

FOR OPTION 3) Explaination is regular language is decidialbe in each and every domain since it is minimum language in chomskey hierarchy….hence option c is decidiable.

FOR OPTION 4) Explaination is recursive language is closed under C,M(complement and membership) and in the question it is asking about complement hence it is decidiable..

CONCLUSION: Statement 3 and 4 are decidiable but option 1 and 2 are not decidiable hence answer is D…..thank you…..

0 votes
0 votes

Correct option (D).

1. Program can loop forever hence it is undecidable 

2. CFL is not closed under Complementation hence undecidable

3. Regular Languages are closed under Complementation hence decidable

4. Recursive languages are closed under Complementation hence decidable . 

Answer:

Related questions

68 votes
68 votes
7 answers
1
48 votes
48 votes
4 answers
3
go_editor asked Apr 21, 2016
13,596 views
Consider the following relations $A, B$ and $C:$ $$\overset{\textbf{A}}{\begin{array}{|c|c|c|}\hline\\\textbf{Id}& \textbf{Name}& \textbf{Age} \\\hline12& \text{A...
42 votes
42 votes
3 answers
4