Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
    
If this is homework, it should be homework-tagged. BTW What have you tried? –  dtldarek Aug 8 '13 at 9:23
add comment

2 Answers 2

Hint:

  • 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|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
add comment

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|improve this answer
1  
The first paragraph really ought to be a comment. –  Brian M. Scott Aug 8 '13 at 17:03
add comment

Your Answer

 
discard

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.