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
  • $\begingroup$ 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. $\endgroup$
    – coffeemath
    Nov 4 '13 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$

  • 3
    $\begingroup$ This accepts the string aabb. So is not the answer to the question. $\endgroup$
    – J Blaz
    Sep 27 '16 at 0:06
  • 1
    $\begingroup$ @JBlaz no it doesn't. This is the correct answer. $\endgroup$ Sep 28 '19 at 19:10
  • $\begingroup$ really nice solution $\endgroup$
    – Daniel
    Oct 18 '19 at 11:55
  • $\begingroup$ 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. $\endgroup$ Nov 19 '21 at 8:45

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

  • $\begingroup$ Makes a lot of sense! $\endgroup$ Mar 29 '20 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- Start Symbol-{S}

Hope this answer is correct ANWAR MULLA (AGCE)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.