6
$\begingroup$

I need to find out if the following problem is decidable:

Given a context-free language $L$, decide whether its complement $\bar{L}$ is also a context-free language.

I am having trouble in defining the $TM$ I need in order to solve this problem. My thinking was to see if it is possible to construct a $TM$ that takes an encoding of a $CFL$ as input and halts in an accept or reject state depending on whether $\bar{L}$ is a $CFL$ or not. Is this line of thinking correct? If so, may I also know how to proceed further.

$\endgroup$
8
  • 1
    $\begingroup$ I don't understand what the algorithmic problem is. Usually it is helpful to list what is the input, and what is the desired output. I see a statement in quotes, but I'm not clear on what the problem is. We don't check answers. Do you have a specific doubt about your approach? Have you tried proving it is undecidable? $\endgroup$
    – D.W.
    Nov 19, 2020 at 8:44
  • $\begingroup$ @D.W. i have corrected the question. I am having trouble in deciding what is the input to the TM i must construct. Is the input to the TM a CFL, such that it halts in an accept state if the complement of the CFL is also a CFL, and halts in a reject state otherwise ? $\endgroup$
    – rohit_r
    Nov 19, 2020 at 8:49
  • $\begingroup$ The first step to trying to find an algorithm is to make sure you can articulate the problem you are trying to find an algorithm for. I still don't understand the problem. What is the input? If the input is a language $L$, how is it represented? What do you want the output to be? What do you want the output to be if $L$ is not a CFL? Have you tried to prove this problem is undecidable? If not, I recommend you give that try, too. $\endgroup$
    – D.W.
    Nov 19, 2020 at 8:53
  • $\begingroup$ @D.W. Sure, I'll give that a try. However, I feel that the question is complete. The question seems to be something similar to "Every CFL is decidable" which has been proved to be true. If by how the langauge L is represented, you mean what is the particular encoding followed, I don't think the answer to my question depends on it. $\endgroup$
    – rohit_r
    Nov 19, 2020 at 9:08
  • $\begingroup$ @gateway2745. I think you are probably misrepresenting the problem. But since you insist that your definition is correct, notice that there exists an algorithm that returns "yes" if and only if the truth value of your implication is "true", and returns "no" otherwise. This algorithm must necessarily be one of the following two: 1) always return "yes", 2) always return "no". If this is unsatisfactory then you'll probably want to revise your question and specify clearly what the input is and what's the expected output as a function of the input, as D.W. said. $\endgroup$
    – Steven
    Nov 19, 2020 at 11:34

1 Answer 1

6
$\begingroup$

Your problem can be formalized in several equivalent ways:

  1. Given a context-free grammar $G$ over $\Sigma$, is $\overline{L(G)} := \Sigma^* \setminus L(G)$ context-free?

  2. Given a PDA $M$ over $\Sigma$, is $\overline{L(M)}$ context-free?

Since we can effectively (and efficiently) translate between the two representations, both problems are equivalent. We stick to the first one.

It is well-known that given a context-free grammar $H$ over $\Sigma$, deciding whether $L(H) = \Sigma^*$ is undecidable. We will reduce this problem to Problem 1.

Let us be given a context-free grammar $H$ over $\Sigma$. If $\Sigma$ is a singleton, then $L(H)$ is regular, and so $\Sigma^* \setminus L(H)$ is also regular and context-free. Otherwise, let $a,b \in \Sigma$ be two distinct symbols. Construct a grammar $G$ over $\Sigma \cup \{\#\}$ (where $\#$ is a fresh symbol) for the language $$ L = (\Sigma^* \setminus \{ww : w \in \Sigma^*\}) \# \Sigma^* \cup \Sigma^* \# L(H). $$ If $L(H) = \Sigma^*$ then $L = \Sigma^* \# \Sigma^*$ is regular, and so its complement is regular and context-free. Otherwise, let $x \notin L(H)$. If $\overline{L}$ were context-free, then so would the following language be: $$ \overline{L} \cap \Sigma^* \# x = \{ww : w \in \Sigma^*\} \# x. $$ This would imply, however, that $\{ww : w \in \Sigma^*\}$ is context-free, which is known to be false.

Summarizing, $\overline{L(G)}$ is context-free iff $L(H) = \Sigma^*$.

Compare Theorems 11–12 in Hendrik Jan's notes.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.