Constructing grammar for $a^ib^j$ / $i\neq j$ I want to construct a grammar for the following regular expression: $a^ib^j / i \neq j$. I did it the following way:
$S_1 \rightarrow aaSb | aaAb$
$A \rightarrow aA | \epsilon$
$S_2 \rightarrow aSbb | aAbb$
$A \rightarrow Ab | \epsilon$
Then:
$S \rightarrow S_1 | S_2$
Is this correct?
 A: No, your grammar can only produce words with more $a$s than $b$s. It can't produce $abb$, for instance.
If $j=0$ is allowed then you'll need to find a way to allow $a$, but otherwise, your grammar produces the alphabet $\{a^ib^j:i,j\in\mathbb{N},i>j\}$, albeit with a bit of redundancy (you don't need two different symbols $A$ and $B$).
Then, try to find a very similar grammar that produces $\{a^ib^j:i,j\in\mathbb{N},i<j\}$.
If you can combine these grammars, then you can find your desired grammar, as:
$$\{a^ib^j:i,j\in\mathbb{N},i>j\}\ \cup \{a^ib^j:i,j\in\mathbb{N},i<j\}\\ =\{a^ib^j:i,j\in\mathbb{N},i\neq j\}$$

A full solution, now you've had another go. (I take it that $a,b$ are not permitted i.e. $i,j\ge 1$.)
$S \rightarrow S_1|S_2$
$S_1\rightarrow aaS_1 b | aaA_1b $
$A_1\rightarrow aA_1 b | \epsilon$
$S_2\rightarrow aS_2 bb | aA_2bb$
$A_2 \rightarrow aA_2 b | \epsilon$
A: Perhaps try a simpler approach. Either there are more as or bs.
Use the regular expression $aa^*(ab)^*|(ab)^*bb^*$ from which we get the following grammar:
$S \leftarrow AC | CB$
$A \leftarrow a | aA$
$B \leftarrow b | bB$
$C \leftarrow \epsilon|aCb$
