Dark Mode

12,718 views

41 votes

Which of the following problems are decidable?

- Does a given program ever produce an output?
- If $L$ is a context-free language, then, is $\bar{L}$ also context-free?
- If $L$ is a regular language, then, is $\bar{L}$ also regular?
- If $L$ is a recursive language, then, is $\bar{L}$ also recursive?

- $1, 2, 3, 4$
- $1, 2$
- $2, 3, 4$
- $3, 4$

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.

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.

1

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

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

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.

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.

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