# Is there a method to generate the complement of a context-free grammar?

Given the languages $$L_0 = {w \in \{0,1\}^*}$$ such that $$w$$ is a palindrome and $$L_1 = {w \in \{0,1\}^*}$$ such that $$w$$ is not a palindrome, meaning $$L_1$$ is the complement of $$L_0$$, we want to find the grammar for both languages. $$G(L_0) = S \to \epsilon | 0S0 | 1S1 | 0 | 1$$ is easy to come up with, but $$G(L_1)$$ is much more complex.

In this case, we have the simple CFG $$G_0$$ and want to find the CFG $$G_1$$ that is its complement which can be much more complex. Is there a method to derive the complement of a CFG?

If $$L_0$$ in a context-free language, this doesn't guarantee that its complement is context free. For example, consider the language $$L_0 = \{a,b,c\}^* \setminus \{a^nb^nc^n : n \geq 0\}.$$ This language is context-free, but is complement (with respect to $$\{a,b,c\}$$) is not.

Another way to formulate your question is as follows: given a context-free grammar for a language $$L$$, is there an algorithm that either constructs a context-free grammar for the complement of $$L$$, or determines that the complement of $$L$$ is not regular? Such an algorithm can be used to decide whether the complement of $$L$$ is context-free. However, this is undecidable, as we now show following Hendrik Jan's notes.

Recall that given a grammar $$G$$ over an alphabet $$\Sigma$$, it is undecidable whether $$L(G) = \Sigma^*$$. Let $$\#$$ be a new symbol, and construct a grammar for the language $$L = L_0 \# \Sigma^* \cup \Sigma^* \# L(G),$$ where $$L_0$$ is a context-free language whose complement is not context-free (if $$|\Sigma| \geq 3$$, we can use the one above, and if $$|\Sigma| = 2$$, we can encode $$a,b,c$$ as $$a,ba,bba$$; if $$|\Sigma| = 1$$ then it is easy to check whether $$L(G) = \Sigma^*$$). If $$L(G) = \Sigma^*$$ then $$L=\Sigma^*\#\Sigma^*$$, and so the complement of $$L$$ is context-free. Otherwise, suppose that $$w \notin L(G)$$. Then $$\overline{L} \cap \Sigma^* \# w = (\Sigma^* \setminus L_0) \# w,$$ which is not context-free, and so $$\overline{L}$$ itself is not context-free (since the context-free languages are closed under intersection with a regular language). This shows that $$\overline{L}$$ is context-free iff $$L(G) = \Sigma^*$$.

The problem of deciding whether $$L(G) = \Sigma^*$$ is actually not recursively enumerable. This means that there is no algorithm which, on input $$G$$, halts iff $$L(G) = \Sigma^*$$ (however, there is a simple algorithm that halts iff $$L(G) \neq \Sigma^*$$, namely go over all words in $$\Sigma^*$$ in parallel, and check whether each of them belongs to $$L(G)$$). Therefore there is no algorithm that, given a context-free grammar for a language $$L$$, halts iff the complement of $$L$$ is context-free.

In other words, even the following solution to your problem does not exist: an algorithm that attempts to construct a context-free grammar for the complement of the given context-free language, and either halts with the grammar, or never halts (if the complement is not context-free).

• I feel stupid, but how is that first language context-free? – cody Jan 6 at 0:09
• That has been answered before several times. – Yuval Filmus Jan 6 at 6:01
• Roughly speaking, either the word is not in $a^*b^*c^*$, or it is of the form $a^ib^jc^k$ where one of the following holds: $i>j,i<j,i>k,i<k,j>k,j<k$. – Yuval Filmus Jan 6 at 6:57
• Oh ok, I see now. I was missing "transitivity of equality" as a hint. – cody Jan 6 at 20:14