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

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