Formal Languages – How to Create a Grammar for Complement of a^nb^n

context-free-grammarformal-languages

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
}

Best Answer

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$

Related Question