Redirected
in Theory of Computation edited by
15,469 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$
in Theory of Computation edited by
by
15.5k views

4 Comments

Yes thank you Sir. I wanted to clarify whether Rice's theorem can be applied on RE languages or (RE and not Rec) languages i.e. languages which are only RE and not anything else.
0
0
If a particular class of language is closed under complement, then we have a machine for that class of language that recognizes its complement and every machine of its kind can do this. This makes it a trivial property and is always decidable.

If its not closed under complement, then we have some machines recognizing the complement but some others don't. So this is a non trivial property now which is undecidable by Rice theorem.
3
3
@Arjun Sir,

If $L$ is a context-free language, then, $\bar{L}$  is also context-free?

DCFL(which is a subset of CFL) is closed under complementation but CFL is not closed under complementation.

So We can’t say Yes/No whether a given CFG language(Maybe a DCFL is given) is closed or not.

Please let me know if it is the correct approach?
0
0

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

4 Comments

@rfzahid

is your comment for me ?

if yes, then clearly see what i am asking.

 

But don't assume "not closed means deciding the class is always undecidable".

i know this statement works on SUBSET property of regular language, but what about other languages ?

RL are not closed under SUBSET property, but on giving two RL's we can say it is true or false ==> even though RL's ae not closed under this property but it is decidable !

0
0
For testing a language to be CFL we need to check if it can be accepted by push down automata or not, which is decidable. So we can conclude that----  “Whether a given any language is Context free language or not..?” is Decidable.  The given language may be CSL, So, “Whether a given any CSL is Context free language or not..?” is Decidable

Now, Let X be a CFL. Then complement of X is a CSL.

Let complement of X is L(a CSL).

As “Whether a given any language is Context free language or not?”   is Decidable  , we can say that “whether L is CFL or not?”  is decidable

Which implies  “whether complement of a CFL is CFL or not?”  is decidable

 

 please tell whats wrong in my approach?
1
1
Decidable is equivalent to saying that there is a finite step algorithm to solve the problem right ??, so then why isn’t 2) correct ??
0
0
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