Redirected
edited by
15,523 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

41 votes
41 votes

CFL’s are not closed under complementation and a program can loop forever. So, it may not produce any output.

Regular and recursive languages are closed under complementation.

Hence, only 3,4 are decidable.

Correct Answer: $D$

edited by
6 votes
6 votes

1.Does a given program ever produce an output?

Here 'Yes' ans is possible but 'No' ans not possible. So, it is Recursive enumerable

2 .If L is a context-free language, then, is L' also context-free?

As context free language is not closed under complementation,  So, CFL not decidable under complementation

3.If L is a regular language, then, L' is also regular?

Regular language closed under complementation. So, it is decidable

4.If L is a recursive language, then, is L'also recursive?

Yes it is decidable

Recursive language is decidable

When the language complemented, the 'Yes' and 'No' ans is also complemented. i.e. 'Yes' becomes 'no' and 'no' becomes 'Yes'. But in complementation of Recursive language we also get 'Yes ' and 'No' answer. So,It is decidable

So, answer is (D)

4 votes
4 votes
CFL’s complementation may or may not be context free so this is a non trivial problem and also undecidable . Regular and recursive languages are closed under complementation.Does a given program ever produce an output? means program is never going to halt so halting problem of TM is undecidable.
2 votes
2 votes

Lets see the options one by one..

1)  is undecidable..This can be correlated to computability of Turing machine..Specifically halting property of Turing Machine which is undecidable..

2) option is also undecidable as complement of context free language may or may not be context free language..So we cannot say with surety that for the class of context free languages , the complementary language will also be context free..

3) and 4)  are decidable as regular and recursive languages are closed under complementation..

Hence D) should be correct answer..

Answer:

Related questions

68 votes
68 votes
7 answers
1
48 votes
48 votes
4 answers
3
go_editor asked Apr 21, 2016
13,583 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