MHB What logic is used to build context free grammar for L= a^m b^n; m>n

[shivajikobardan]

I have the solution but I am unable to decode the solution, how did we come up here? can you tell me that?

 

[Evgeny.Makarov]

Is the problem "Derive $aaab$? Then you are given an explicit derivation. Do you know the definition of a derivation in the context of grammars? What exactly is not clear?

 

[shivajikobardan]

No. I understand derivation. My problem is that I am not understanding how we came up to this solution of CFG. I want that problem solving skill to learn rather than trying to memorize this. So I am asking this. There must be some patterns of questions there right? Can you guide me a bit in this question?

 

[Evgeny.Makarov]

Applying rule $S\to aS$ $n$ times where $n\ge0$ allows building strings of the form $a^nS$ from $S$. Then the only different thing to do is to apply $S\to aT$ to produce $a^{n+1}T$. After that, applying $T\to aTb$ $m$ times where $m\ge0$ produces $a^{n+1}a^mTb^m$. Finally, $T\to\varepsilon$ finishes the derivation and produces $a^{n+m+1}b^m$. These are the only strings (for some $n,m\ge0$) that one can generate using this grammar.