3
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ I feel stupid, but how is that first language context-free? $\endgroup$ – cody Jan 6 at 0:09
  • $\begingroup$ That has been answered before several times. $\endgroup$ – Yuval Filmus Jan 6 at 6:01
  • $\begingroup$ 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$. $\endgroup$ – Yuval Filmus Jan 6 at 6:57
  • $\begingroup$ Oh ok, I see now. I was missing "transitivity of equality" as a hint. $\endgroup$ – cody Jan 6 at 20:14

Your Answer

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

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