How to create a grammar for complement of $a^nb^n$?

Consider this logic: a sentence in the complement of $L$ either should start with $b$ or end in $a$ or if it starts with $a$ and ends with $b$ the substring between the two must not be in $L$ (should be in the complement of $L$). So we can write:

$S\to bA|Aa|aSb$

$A \to aA|bA|\epsilon$

We can break this language into the union of several simpler languages:

L = { $a^i b^j$ | i > j } ∪ { $a^i b^j$ | i < j } ∪ $(a ∪ b)^∗b(a ∪ b)^∗a(a ∪ b)^∗$.

That is, all strings of a’s followed by b’s in which the number of a’s and b’s differ, unioned with all strings not of the form $ a^ib^j$.

First, we can achieve the union of the CFGs for the three languages:

S → $S_1|S_2|S_3$

Now, the set of strings { $a^ib^j$ | i > j } is generated by a simple CFG:

$S_1 → aS_1b|aS_1|a$

Similarly for { $a^ib^j$ | i < j }:

$S_2 → aS_2b|S_2b|b$

Finally, $(a ∪ b)^∗b(a ∪ b)^∗a(a ∪ b)^∗$ is easily generated as follows:

S3 → XbXaX

X → aX|bX|ϵ

---

Source: http://cseweb.ucsd.edu/classes/su99/cse105/sample2.pdf