0
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ There are quite a few very similar questions around, e.g. this and this. $\endgroup$
    – Raphael
    Commented Mar 8, 2013 at 20:41

1 Answer 1

Reset to default
0
$\begingroup$

Hint: Start with a CFG for the language $\{ a^{n+t} b^n : n \geq 0, t \geq 1 \}$.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Does this really count as an answer? $\endgroup$
    – John Kemeny
    Commented Mar 8, 2013 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$
    – John Kemeny
    Commented Mar 8, 2013 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
    Commented Mar 8, 2013 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$
    – Yuval Filmus
    Commented Mar 8, 2013 at 19:51
  • $\begingroup$ @Dylan The trick is to take $m = n+t$ where $t \geq 1$. This ensures that $n \neq m$. $\endgroup$
    – Yuval Filmus
    Commented Mar 8, 2013 at 19:52

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