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$