# Language generated by $S \to aAb|Sb$, $A \to aAb|ab$

Let $$G = (\{A,S\}, \{a,b\}, S, P\}$$ be the grammar with the following productions: \begin{align} & S \to aAb | Sb \\ & A \to aAb | ab \end{align}

1. What is the language $$L(G)$$ generated by the grammar?

Here is my attempt. I think that the language generated by $$G$$ is $$L= \{a^nb^{n+k} \mid n\geq2,k\geq0. \}$$ I need to prove that $$L = L(G)$$ by induction on length, but I don't know how to do it properly because I have two parameters ($$n,k$$). There also need to be two directions to the proof.

I found this post, but it is of no help to me.

What is the base case? I tried looking about distinguishing whether the length is even or odd, and I think I got the pattern between $$(n,k)$$ correctly, but I really don't have a clue how to start the proof.

Start by showing that $$L(A)$$ (the language generated by the grammar if the starting symbol is $$A$$) is $$L_A = \{ a^n b^n \mid n \geq 1 \}$$. You prove this by double inclusion:
• In order to prove that $$L_A \subseteq L(A)$$, prove by induction on $$n$$ that $$A \Rightarrow^* a^nb^n$$.
• In order to prove that $$L(A) \subseteq L_A$$, prove by induction on the length of the derivation that if $$A \Rightarrow^* \alpha$$ then either $$\alpha = a^n b^n$$ for some $$n \ge 1$$, or $$\alpha = a^n A b^n$$ for some $$n \geq 0$$. (In fact we won't need this direction, but it's good practice.)
Now we can show that $$L = L(G)$$, again by double inclusion:
• In order to prove that $$L \subseteq L(A)$$, prove by induction on $$k$$ that $$S \Rightarrow^* aAb^{k+1}$$.
• In order to prove that $$L(A) \subseteq L$$, prove by induction on the length of the derivation that if $$S \Rightarrow^* \alpha$$ then either $$\alpha = S b^k$$ for some $$k \geq 0$$, or $$\alpha = a^{n+1}Ab^{n+k+1}$$ for some $$n,k \geq 0$$, or $$\alpha = a^{n+2} b^{n+k+2}$$ for some $$n,k \geq 0$$.