Finding a context-free grammar for a language with a different word count condition

Question

I want to find a context-free grammar with the condition, that the grammar has to be the complement of a language with the same word count.

So a language with the same word count can be specified easy with this grammar:

• Set of variables

  V := {S}

• Set of terminals

  Σ := {a,b}

• Set of relations

  S → ""

  S → aSbS

  S → bSaS

• Start variable

  S

Words in language: ab,abba,aaabbb ...

---

What is the complement of this language (where the word count is not equal), specified in a context-free grammar?

Answer 1

HINT: Split the grammar into two parts, one generating $L_A$, the set of strings with more $a$’s than $b$’s, the other generating $L_B$, the set of strings with more $b$’s than $a$’s. If $A$ and $B$ are the initial symbols for these subgrammars, you’ll need productions $S\to A\mid B$.

Let $L_0$ be the set of strings with equal numbers of $a$’s and $b$’s. Every string in $L_A$ has the form $uav$, where $u\in L_0$ and $v\in L_A\cup L_0$ (why?), so you’ll want productions $A\to EaA\mid EaE$, where $E$ is the initial symbol for a subgrammar that generates $L_0$; you already know this grammar, since it’s essentially the one in your question.

You can handle $L_B$ similarly.