Proving L(G) = L using induction and deriving a schema Consider the following grammar G:
S -> aS
  -> aTb
  -> a
T -> aTb
  -> a

How would I prove that L( G) = L where L = { a^m b^n | 0 <= n < m} in two steps as follows.
a) By induction that L( G) SubsetEq L considering the following equality:
0 <= |w|_b < |w|_a + |w|_S + |w|_T

  where w is any sentential form.

for this, i started with the basis step as follows: 
Basis: Let the lenght of the derivative = 1, therefore:

    S => aS,  |w|_b = 0, |w|_a = 1, |w|_S = 1, |w|_T = 0, and the inequality is true

    S => atb,   |w|_b = 1, |w|_a = 1, |w|_S = 0, |w|_T = 1, and the inequality is true

    S => a,   |w|_b = 0, |w|_a = 1, |w|_S = 0, |w|_T = 0, and the inequality is true

which proves that the basis step is true, but how would I go about proving the inductive step?
b) And that L SubsetEq L( G) by finding a derivation schema for 
      any w in L.
Ok, so with everyones help, I managed to get a bit of the solution for part b.
If x = a^m+n b^n and n > 0, then:
S => a^m-1 S using S -> aS
  => a^m Tb using S -> aTb
  => a^m+n-1 Tb^n using T -> aTb
  => a^m+nb^n using T -> a 
If x = a^n, then:
S = a^n-1 S using S -> aS
S = a^n using S -> a

But from here, I am not sure how to get the final solution in order to prove that L(G) = L. From what I understand, the final step should result in S=a^m b^n correct?
 A: For the induction step of the first argument you need to assume that the statement is true for all derivations of length $n$ and show that it’s true for all derivations of length $n+1$. 
Suppose that $S\Rightarrow^{n+1} w$. Then there is a word $v$ such that $S\Rightarrow^n v\Rightarrow w$. The last step in the derivation uses one of the five productions, and you need only see what each of the productions does to the number of $a$s, the number of $b$s, the number of $S$s, and the number of $T$s. For example, if the last step used the production $S\to aTb$, then $|w|_a=|v|_a+1$, $|w|_b=|v|_b+1$, $|w|_S=|v|_S-1$, and $|w|_T=|v|_T+1$, so
$$\begin{align*}
|w|_a+|w|_S+|w|_T&=(|v|_a+1)+(|v|_S-1)+(|v|_T+1)\\
&=|v|_a+|v|_S+|v|_T+1\\
&>|v|_b+1&\text{induction hyp.}\\
&=|w|_b\;,
\end{align*}$$
as desired. It now follows that if $w\in L(G)$, then $|w|_b\le|w|_a+|w|_S+|w|_T=|w|_a$. To complete the proof that $L(G)\subseteq L$, you must show that if $w\in L(G)$, then $w=a^mb^n$ for some $m,n\ge 0$, i.e., that every $a$ in $w$ comes before every $b$. You can also prove this by induction on the length of the derivation.
To show that $L\subseteq L(G)$, you’re to come up with an algorithm for deriving each $a^mb^n$ with $n<m$. If $n=0$, for instance, and $m\ge 1$, we can derive $a^mb^n=a^m$ by applying $S\to aS$ $m-1$ times and then applying $S\to a$:
$$\underbrace{S\Rightarrow aS\Rightarrow a^2S\Rightarrow\ldots\Rightarrow a^{m-1}S}_{m-1\text{ steps}}\Rightarrow a^m\;.$$
To complete the proof, you need to do something similar for the case in which $n>0$. It may help to let $k=m-n$ and to think about how to derive $a^{n+k}b^n$, where $k$ is a positive integer.
A: If $x=a^{m+n}b^n$ and $n>0$, then we can derive it by these steps from rules of G:


*

*Use rule $S\rightarrow aS$, $m-1$ times to derive $a^{m-1}S$.

*then use rule $S\rightarrow aTb$ to derive $a^{m}Tb$.

*then use rule $T\rightarrow aTb$, $n-1$ times to derive $a^{m+n-1}b^n$.

*and at last use rule $T\rightarrow a$ to derive $a^{m+n}b^n$


If $x=a^n$, then we can derive it by these steps from rules of G:


*

*Use rule $S\rightarrow aS$, $n-1$ times to derive $a^{n-1}$.

*then use rule $S\rightarrow a$ to derive $a^n$

