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?

  • $\begingroup$ There are quite a few very similar questions around, e.g. this and this. $\endgroup$
    – 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 \}$.

  • $\begingroup$ Does this really count as an answer? $\endgroup$
    – Pål GD
    Mar 8 '13 at 19:15
  • $\begingroup$ This does not provide an answer to the question. To critique or request clarification from an author, leave a comment below their post. $\endgroup$
    – Pål GD
    Mar 8 '13 at 19:16
  • $\begingroup$ 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. $\endgroup$
    – dtg
    Mar 8 '13 at 19:24
  • $\begingroup$ @PålGD This looks like a homework question to me, so my (personal) policy is to only give hints. If you disagree, you can always downvote. $\endgroup$ Mar 8 '13 at 19:51
  • $\begingroup$ @Dylan The trick is to take $m = n+t$ where $t \geq 1$. This ensures that $n \neq m$. $\endgroup$ Mar 8 '13 at 19:52

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