# Context-free grammar for $\{a^x b^y : x \neq y\}$

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?

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