The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+21 votes
1.7k views

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, $\bar{L}$ is 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
asked in Theory of Computation by Veteran (355k points)
edited by | 1.7k views
+4
1. L is set of all program. For this language if any program ever produce an o/p or not is non trival property. So according to Rice theorm it is Undecidable..

2. L is set of all CFL. For this language whether any member's complement is CFL or not is non trival property. As CFL are not closed under complement. 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 is trival property. As RL are  closed under complement. 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 trival property. As Recursive languages are  closed under complement. So According to Rice theorem it is Decidable.
0

mystylecse Can Rice's Theorem be applied on CFL's or on languages which are only recursively enumerable?

0
^Any CFL is also recursively enumerable. And if you say Rice's theorem statement - it clearly says where it can be applied.
0
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.

3 Answers

+24 votes
Best answer

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.

answered by Boss (14.2k points)
edited by
+23

"CFL’s are not closed under complementation"

Had CFL been closed  under complementation, we could say deciding whether complement of a CFL is CFL is trivially decidable. But, because it is not closed, we now have a decision problem in our hand. We cannot simply say that this is undecidable. It must be proved so.

This proof has been given in automata text books but I don't remember that exactly. I think it follows from Griebach's theorem.  Anyway it is slightly over bachelors level. And because of the given choices you can answer this even without knowing this proof. But don't assume "not closed means deciding the class is always undecidable".

0
i was also in a confusion to post this answer but i found 3,4 more appropriate
0
  1. Does a given program ever produce an output?
    is also decidable. Correct??
+1
Undecidable ..as a machine can get into an infinite loop and not printing a single character
+1
I think Option 1 is nothing but a Halting Problem, which is undecidable.
0

@Arjun sir, "CFL’s are not closed under complementation"  using this statement we can not say that L' (complement of L) is CFL or not, hence we have decision problem in our hand.

But we have membership algorithm for CFL ie determining particular language is CFL or not is decidable. So L' is CFL or not is always decidable irrespective of L.

+7
Membership algorithm is for checking membership of a "string" in L. For CFL this is decidable. That does not make the problem of deciding if a given language is CFL or not decidable.
+1
ya my bad :(

thnx for making it more clear :)
0
@Arjun Sir

As you say "because of the given choices you can answer this even without knowing this proof"

How can we choose option D instead of C because of the given options?
0
@arjun sir, "not closed means deciding the class is always undecidable", can you give some examples?
+2
Option 1: checking program produces o/p is same as checking TM halts----which is UD.
Option 2: L is context free then $\bar{L}$ is definitely CSL.  checking $\bar{L}$ (which is CSL) is CFL or not, this is undecidable because i can't even check that two PDAs are equal then how can i check that given LBA and PDA are accepting same language.

@Arjun sir, plz verify 2nd point.
+1

@Sachin Mittal 1 ji, 

checking L' (which is CSL) is CFL or not, this is undecidable because i can't even check that two PDA's are equal then how can i check that given LBA and PDA are accepting same language.

I have one doubt, How will you obtain PDA and LBA for comparison ?

+1
We can proof option 1 as undecidable using diagonal cantor.
+4 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)

answered by Veteran (91.5k points)
+2 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.
answered by Active (2.1k points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

37,939 questions
45,453 answers
131,194 comments
48,209 users