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

Solution 1:

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$

Solution 2:

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

Solution 3:

The strings not of form $a^nb^n$ come in several groups.

A string starting with $b$ can be gotten via $S \to bS_1$, then $S_1 \to aS_1|bS_1|\varepsilon $

A string may have a positive number of $a$, then a positive number of $b$, then a positive number of $a$ and then anything. This one takes more steps: $S\to aS_2$, then $S_2 \to aS_2|bS_3$, then $S_3 \to bS_3|aS_4$, then $S_4 \to aS_4|bS_4|\varepsilon.$

Remaining strings in the complement have $a$'s followed by $b$'s but either more $a$ on the left or more $b$ on the right. For more $a$ on the left, use $S \to aS_5,$ then $S_5 \to aS_5|aS_5b|\varepsilon$ Finally for more $b$ on the right use $S \to S_6b,$ and then $S_6 \to S_6b|aS_6b|\varepsilon.$

I'm not an expert on this topic, but the above looks intuitively to me like it covers all the strings in the complement of $a^nb^n$ while not letting any of the latter be produced.