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 '19 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$ – Florian Oct 27 '19 at 12:27
  • $\begingroup$ I don't understand your objection. Inequality is also a form of correlation. $\endgroup$ – rici Oct 27 '19 at 12:37
  • $\begingroup$ Ok, maybe I misunderstood your hint. Could you further elaborate on how to actual implement it? $\endgroup$ – Florian Oct 27 '19 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$ – Yuval Filmus Oct 27 '19 at 18:37

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

| cite | improve this answer | |
  • 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 '19 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.