Context free grammar for a language that is a complement of another

Question

Create a context free grammar for L. $$ L=\{a^nb^mc^k | n+m \neq k\} $$

First I tried to create a CNF for a language that accepts strings in which $n+m = k$. I got this:

$$ S \rightarrow aAc $$ $$ A \rightarrow aAc \mid B $$ $$ B \rightarrow bBc \mid \epsilon $$ to create a CNF for $L$, I wanted to add a new start state that basically adds another symbol to the strings accepted by the CNF above. I can add as and cs with no problem but don't know how to add bs since b is in the middle.

Answer 1

I would like to add that the language $L_0=\{a^n b^m c^k\;|\;n+m=k\}$ is the deterministic context-free language, and a DPDA can be constructed recognizing $L_0$ by the final state. Then we can use the closure property of DCFLs under the complement and obtain a DPDA for $L$ swapping the final and non-final states in the initial DPDA (with a little mess with the trap state).

The main construction is rather straightforward, but it is refined in the two following aspects:

1. The new stack symbol $A$ is introduced, marking the very first occurrence of either $a$ or (if $a$ block is empty) $b$. If we use the single stack symbol $B$, then we would also have a DPDA (having an $\epsilon$-transition to the state $Q_4$ by the stack symbol $Z_0$), but that DPDA is not so convenient to construct a complement, since it contains $\varepsilon$-transitions between the final and the non-final state. The DPDA below has no such transitions, distinguishing the last pop operation.
2. We omitted most transitions to the trap state $T$, because these transitions correspond to the words not belonging to the language $a^* b^* c^*$ (and the initial language $L$ is a subset of this regular language, thus these transitions kick from $L$ as well).

Now simply swap the final and non-final states and get the DPDA for the required language. If you like to construct PDAs, this technique works rather well for recognizing complements of the deterministic languages, but since you ask not for a PDA, but for a CFG, you still have to make the PDA$\rightarrow$CFG transition. In the case considered, it is again quite straightforward (and gives almost the same result as the direct CFG construction): all what you need is to consider the stored $A$ and $B$ stack symbols as the nonterminals which derive a single letter $c$ if popped and $\varepsilon$ otherwise.

Btw, the PDAs above allow $n$, $m$, and $k$ to be zeros.

Answer 2

There's no procedure for creating a context-free grammar for the complement of a context-free language, because the complement of a context-free language might not be context-free, and the question of whether a language is context-free is not decidable.

Of course, particular context-free languages (and some languages which are not context-free) do have context-free complements, and this is an example of such a language. Indeed, as @Tonita observes in her excellent answer, $L^C$ is a deterministic context-free grammar, which are closed under complement. So that's not entirely a dead end.

But on the whole, it's rarely helpful to try to start with a grammar for $L$ and transform that into a grammar for $L^C$, since the latter might not even exist, and even if it dies, mechanically generating it could be a lot of work.

Here's another approach which often works for problems like this. When trying to deal with languages whose descriptions involve inequalities, it's often useful to remember that $i\ne j$ is the union of the two predicates $i<j$ and $i>j$, and furthermore that $i>j$ is the same as $\exists k>0 \mid i = j + k$. Finally, $a^{j+k} = a^ja^k$. That should be enough to quickly find the solution.