Proving L(G) = L using induction and deriving a schema

Question

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?

Answer 1

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.

Answer 2

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$