# Context free grammar for {a^mb^n | m ≠ n} [duplicate]

I need to find a context-free grammar for the above expression, $a^{m}b^{n}$ for the set $L = \left\{{a, b}\right\}$, but I am having difficulty accounting for the condition $m \neq n$.

This is what I have so far, but it clearly doesn't satisfy the above condition:

\begin{align} &S \rightarrow aAb &\\ &S \rightarrow a &\\ &S \rightarrow b &\\ &A \rightarrow aA &\\ &A \rightarrow bA &\\ &A \rightarrow \lambda \\ \end{align}

I have spent about an hour on this, and haven't found a solution. Any ideas?

• There are quite a few very similar questions around, e.g. this and this. – Raphael Mar 8 '13 at 20:41

Hint: Start with a CFG for the language $\{ a^{n+t} b^n : n \geq 0, t \geq 1 \}$.
• I understand what you are saying, and I did try to find a grammar for this, but I run into the same problem -- how to ensure that $m$ and $n$ are not the same number. With my above grammar, any number of $a$s or $b$s is valid, and $a$s and $b$s can have the same degree, which is obviously wrong. – dtg Mar 8 '13 at 19:24
• @Dylan The trick is to take $m = n+t$ where $t \geq 1$. This ensures that $n \neq m$. – Yuval Filmus Mar 8 '13 at 19:52