2.4k 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
• 🚩 Edit necessary |
edited | 2.4k 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.
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.

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.5k points) 1 flag:
✌ Edit necessary (Utkarsh Joshi)

edited
+26

"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

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?
+3
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.
0

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

@Arjun  sir, can you elaborate more on this statement ?

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.
0

@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 !

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

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

1
2