Lately I came across a problem:

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

And I need to comment on its decidability. Now I know that context free language is not closed under complementation. Had it been so, then this decision problem would have been trivially decidable. [In the sense that we could design a Turing Machine for this problem and allow it to always answer "YES".]

Few of peers make a wrong logic behind the problem as follows. They say that the problem below is undecidable since CFLs are not closed under complementation. This logic/reasoning seems utter non-sense to me.

Yet few other peers try commenting about the decidability of the problem using Rice Theorem. They argue as follows:

Let $L$ be set of all CFLs. For this language whether any member's complement is CFL or not is non trivial property. As CFL are not closed under complement. So According to Rice theorem it is undecidable.

But this above argument also does not convince me. I mean is it correct in the first place? I know the Rice Theorem and it states that :

Any non trivial property of Recursively Enumerable Languages is undecidable.

And my peer probably justifies this argument about Rice Theorem saying that all CFLs are also RE languages. But as far as I know, the "property" talked about in Rice Theorem is a predicate where the universe of discourse is the set of RE languages. Now if I reduce/chop this universe of discourse to contain only CFLs, then would things remain the same? I do not think so, [I might be wrong however.] in the sense that now we are dealing with just a smaller fraction of the entire set. [Like, for instance, the set $\mathbb{N}$ is closed under addition, but the set $\{1,2,..,10\}$ is not.]

To apply Rice Theorem, I would defined the language of the property as:

$$L_p=\{\langle M \rangle | \text{ L(M) is a context free language and $\ \overline{L(M)}$ is context free}\}$$

Here the language $L_p$ is undecidable, because the property that "a RE language is context free and its complement is context free", is non-trivial. But this non triviality arises primarily due to the check of RE language being context free. Is the actual decision problem correctly addressed by the $L_p$ above?

Moreover for decidability question I usually try to design a TM machine, but in this decision problem I am having no clue as to how to proceed? If I am given a CFL (using a finite description of course), then how do I design the TM to find the complement of this finite description? Once this complementation is done, we can check whether the language produced is a CFL. (But how?) This is a thought process which I have in my mind, but I cannot proceed.

Or is this decision problem problem much more notorious than it seems to be and do we next level thinking beyond the possible approaches which came to my mind? Please help.

PS: In the beautiful answer to a similar question, I have got the idea of how to answer the decidability question, but what still remains mysterious to me is the approach which my peers were following using Rice-Theorem, (is it at all correct?), and what could have been a possible raw TM machine approach? I guess this is how my question (probably) slightly differs from this...


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.