GATE CSE 2012 | Question: 24

Question

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?

• A. $1, 2, 3, 4$
• B. $1, 2$
• C. $2, 3, 4$
• D. $3, 4$

Comments

Optional 2 is undecidable

https://cs.stackexchange.com/questions/132411/deciding-whether-complement-of-context-free-language-is-context-free

---

Option 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. According to Rice theorem it is Decidable.

---

Statement 1 is classic TM HALTING PROBLEM hence undecidable

A decision problem is called trivially decidable if the answer to the question is statically identical for every single instance belonging to that language family. You don't need a complex algorithm or Rice's Theorem; the mathematical definition of the class answers it for you.

• For Statement 3: Regular languages are closed under complement. By absolute definition, if $L$ is regular, $\bar{L}$ is always regular. The answer is a hardcoded "YES" for every single regular language. Hence, it is decidable.

• For Statement 4: Recursive languages are closed under complement. If you have a Halting Turing Machine for $L$, you simply swap the accept and reject states to get a machine for $\bar{L}$. The answer is a hardcoded "YES" for 100% of recursive languages. Hence, it is decidable.

Non-Trivial Properties outside RE 

What happens if a language family is not closed under an operation? This is the conceptual zone.

Context-Free Languages are not closed under complement. This means:

• For some CFLs, the complement is still a CFL (e.g., if $L = a^*$, then $\bar{L}$ is regular, which means it is also a CFL).

• For other CFLs, the complement is completely non-CFL (e.g., if $L = \{a^n b^n c^m\} \cup \{a^m b^n c^n\}$, its complement requires tracking two sets of counts simultaneously, which cannot be done with one stack).

Because the answer can be "YES" for some context-free languages and "NO" for others, this is a non-trivial property of Context-Free Languages. NOW DUE TO THIS THE ALGORITHM CANNOT TRIVIALLY DECIDE AND SINCE IT CANNOT TRIVIALLY DECIDE IT WILL HAVE TO INSPECT ONE BY ONE INFINITELY BY WHICH WE KNOW THAT IT IS OF THE FORM OF TM HALTING PROBLEM AS IF WE CAN SAY GIVEN CFG IS COMPLEMENT OF THE OTHER CFG THAT MEANS WE HAVE CHECKED ALL STRINGS IN SIGMA STAR (KLEENE STAR) THAT IS WE HAVE SOLVED THE TM HALTING PROBLEM INDIRECTLY AS WE CAN SAY FOR EACH STRING WHETHER IT WILL HALT OT NOT!

 

TO SUMMARISE: 

It tells us that we cannot use a hardcoded shortcut. * Look at a Closed Property (Regular Complements): If the question is "If $L$ is regular, is $\bar{L}$ regular?", the answer is always YES for 100% of inputs. An algorithm doesn't need to look at the machine; it can just print "YES" and halt. It is trivially decidable.

• Look at a Non-Closed Property (CFL Complements): Because the answer is "YES" for some and "NO" for others, an algorithm cannot cheat. It is forced to inspect the unique, individual structure of the grammar to figure out which case it falls into.

Because the algorithm is forced to analyze the specific language of the grammar across an infinite string space, we are able to build that hybrid reduction trap ($L_{\text{new}}$) from the previous step, perfectly chaining it back to the Halting Problem.

Answer 1

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$

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 !

---

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?

---

Decidable is equivalent to saying that there is a finite step algorithm to solve the problem right ??, so then why isn’t 2) correct ??

Answer 2

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)

Answer 3

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.

Answer 4

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 5

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.

Answer 6

For any language, if algorithm is possible then that language is "recursive" (DECIDABLE) as algorithm will always halts
And for any language if program is possible then that language is RE (UNDECIDABLE) as program may or may never HALT

So option 1, is "undecidable" as program may or may never give output
Option 2, is also Undecidable as CFL is not close under complement, thus if L is CFL then L' may or may not be CFL, so it is "undecidable"
Option 3, regular language is close under complement, thus it is obvious yes problem, hence it is "decidable"
Option 4, recercive is alse close under coplement, thus it is obvious yes problem, hence it is "decidable"

so, option D is correct