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$


$S \rightarrow S_1 | S_2$

Is this correct?

  • 1
    $\begingroup$ How would you deal with $abb$? Assuming that $S$ is the start symbol. $\endgroup$
    – copper.hat
    Mar 6, 2022 at 21:42

2 Answers 2


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$

  • $\begingroup$ Thanks, I have updated my answer, like that? $\endgroup$
    – Papa
    Mar 6, 2022 at 21:56
  • $\begingroup$ Do I have both right and left linear grammar combined there? $\endgroup$
    – Papa
    Mar 6, 2022 at 21:57
  • $\begingroup$ @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). $\endgroup$
    – 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$


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .