snippetMinor
Is there a method to generate the complement of a context-free grammar?
Viewed 0 times
themethodfreegenerategrammarcontextcomplementthere
Problem
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?
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?
Solution
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).
$$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).
Context
StackExchange Computer Science Q#133797, answer score: 2
Revisions (0)
No revisions yet.