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

I've got a language L: $$\Sigma = \{a,b\} , L = \{a^nb^n | n \ge 0 \}$$

And I'm trying to create a context-free grammar for co-L.

I've created grammar of L:

P = {
S -> aSb
S -> ab | epsilon
}


In co-L, I don't know how to ensure, that there won't be the same number of a,b. Should I create something like this?

P = {
S -> aSb
S -> a | b | aS | bS
}

• In your grammar for $L$ you can drop the option $S\to ab$ since that's covered by $S \to aSb \to a \varepsilon b$. The complement would include things like $abbabaabb$ and so on, maybe there's a trick for such a thing but I don't see it. Commented Nov 4, 2013 at 3:48

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$

• This accepts the string aabb. So is not the answer to the question. Commented Sep 27, 2016 at 0:06
• @JBlaz no it doesn't. This is the correct answer. Commented Sep 28, 2019 at 19:10
• really nice solution Commented Oct 18, 2019 at 11:55
• Someone might think that aabb would be generated by S -> aSB -> aaSbb but notice that S doesn't generate the empty string so aabb can't be generated this way. Commented Nov 19, 2021 at 8:45
• @Nezuko The second step in your derivation is not possible with the grammar because you cannot replace $S$ with $aA$. Commented Nov 29, 2022 at 5:09

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|ϵ

• Makes a lot of sense! Commented Mar 29, 2020 at 0:51

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.

a^n b^n means equal number of a following equal number of b

Grammar g={N,T,P,S}

N- Non Terminals-{A}

T- Terminals-{a,b,epsilon}

p- Production

S->A

A->aAb

A->Epsilon(^)

S- Start Symbol-{S}

Hope this answer is correct ANWAR MULLA (AGCE)

• Please be clearer with your post, and format mathematics using MathJax Commented Apr 25, 2017 at 4:43