# 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?

• How would you deal with $abb$? Assuming that $S$ is the start symbol. Mar 6, 2022 at 21:42

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.

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

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$$

• Thanks, I have updated my answer, like that?
– Papa
Mar 6, 2022 at 21:56
• Do I have both right and left linear grammar combined there?
– Papa
Mar 6, 2022 at 21:57
• @user18309957 see my edited response. No part of the grammar is right/left-linear (as this would require all the $a,b$ to be either to the right or to the left of the state symbols).
– A.M.
Mar 6, 2022 at 22:03

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$$