Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Obtain a grammar for the language

  • $L = \{a^m b^n \mid m ≠ n , m > 0 , n > 0 \}$.

Please help me with the solution.

share|cite|improve this question


  • Let $L_0 = \{a^nb^n \mid n > 0\}$.
  • Let $L_1 = \{a^k \mid k > 0\} \circ L_0$ and $L_2 = L_0 \circ \{b^k \mid k > 0\}$.
  • Then $L = L_1 \cup L_2$.

I hope this helps $\ddot\smile$

share|cite|improve this answer
You want $L_2=L_0 \circ\{b^k\mid k>0\}$. – Rick Decker Aug 8 '13 at 14:07
@RickDecker Yeah, thanks. – dtldarek Aug 8 '13 at 14:25

Am I right in assuming this is homework? If so, please use the homework-tag.

Since $m\neq n$, there are two situations: $m > n$ or $m < n$. Each case can be treated seperately. In the first case, each word must contain $aab$, since $m,n>0$. So start with the string $aab$, and in each step add either both an $a$ and a $b$, or just add an $a$. This information is all you need, so try writing the productions by yourself.

share|cite|improve this answer
The first paragraph really ought to be a comment. – Brian M. Scott Aug 8 '13 at 17:03

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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