Constructing grammar for $a^ib^j$ / $i\neq j$

Question

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?

Answer 1

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$

Answer 2

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$