I am trying to create a context free grammar in Extended Backus–Naur form, which starts with a non-empty sequence of a's and is followed by a non-empty sequence of b's. With the special condition that the number of b's has to be unequal to the number of a's.

Thus, the grammar should generate words like:

  • aaaabbb
  • aaabb
  • abbb

So basically I could do something like this:

$\ G=(N,T,P,S)$

$\ N = \{S\}$

$\ T = \{a,b\}$

$\ P = \{S=aa(S|\epsilon)b\}$

But then the words would always have $\ 2n$ a's and n b's:

  • aab
  • aaaabb
  • aaaaaabbb

So how is it possible to make the number of a's uncorrelated of the number of b's, without being equal?

  • 1
    $\begingroup$ Hint: if $n\ne m$ then either $n\lt m$ or $n\gt m$. $\endgroup$
    – rici
    Oct 26, 2019 at 21:00
  • $\begingroup$ I could make one definition with more As and one with more Bs, but then the number of characters is still correlated $\endgroup$
    – Flo
    Oct 27, 2019 at 12:27
  • $\begingroup$ I don't understand your objection. Inequality is also a form of correlation. $\endgroup$
    – rici
    Oct 27, 2019 at 12:37
  • $\begingroup$ Ok, maybe I misunderstood your hint. Could you further elaborate on how to actual implement it? $\endgroup$
    – Flo
    Oct 27, 2019 at 16:22
  • 2
    $\begingroup$ Possible duplicate of Context Free Grammar for language $L=\{a^ib^j \mid i,j \ge 0; i \ne 2j\}$ $\endgroup$ Oct 27, 2019 at 18:37

1 Answer 1


Let $L = \{a^n b^n : n \in \mathbb N\}$. Your language can be written as $a^+L \cup Lb^+$, and this leads to the following grammar: $$ \begin{align} &S \to AT \mid TB \\ &T \to aTb \mid \epsilon \\ &A \to aA \mid a \\ &B \to bB \mid b \end{align} $$ We can save a nonterminal by factoring $L$ differently: $$ L = \{a^na^mb^n : n \geq 0, m \geq 1\} \cup \{a^nb^mb^n : n \geq 0, m \geq 1\}. $$ This leads to the following grammar: $$ \begin{align} &S \to aSb \mid A \mid B \\ &A \to aA \mid a \\ &B \to bB \mid b \end{align} $$ There are many other possible variants, for example: $$ \begin{align} &S \to A \mid B \\ &A \to aAb \mid aA \mid a \\ &B \to aBb \mid Bb \mid b \end{align} $$

  • 2
    $\begingroup$ All of your solutions produce the sentences $a^i$ and $b^i$ for $i\ge 1$, although the OP requests $a^ib^j, i,j\ge 1, i\ne j$. Of course, the fixes are minor. For the first one, you can change $T\to aTb\mid\epsilon$ to $T\to aTb\mid ab$. $\endgroup$
    – rici
    Oct 28, 2019 at 20:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.