Obtain a grammar for the language (i) L = {a ^m b ^n ; m ≠ n ; m , n > 0 }

Question

Obtain a grammar for the language

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

Please help me with the solution.

Answer 1

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$

Answer 2

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.