Given that I have the grammar$\qquad\displaystyle G_1 = (\{a, b, c, d\}, \{S, X, Y \}, S, \{S  XY, X  aXb, X  ab, Y  cYd, Y  cd\})$,how am I supposed to prove that$\qquad\displaystyle S(G1)  \{a^{n+1} b^{n+1} c^{m+1} d^{m+1} \mid n, m  0\}$by using Induction?
How do I use induction to show that the language of a grammar is contained in a given set?
formal grammars;proof techniques;induction
When proving something about a language generated by a grammar, your induction should be on the number of derivation steps.Here, the induction hypothesis should be:$S=>^i a^kAb^kc^jBd^j $ for $i,j < i, A \in \{ X, \epsilon\}, B \in \{ Y, \epsilon\}$ .base: for $i=1$ we have that $S=>^1 XY = a^0Xb^0c^0Yd^0$. and the hypothesis holds.step: Assume $S=>^i a^kXb^kc^jYd^j => a^{k'}Xb^{k'}c^{j'}Yd^{j'}$. We have 4 case for the last derivation step. if it was $X \rightarrow aXb$, then $k' = k+1$ and $S=>^{i+1} a^{k+1}Xb^{k+1}c^jYd^j$Similar case if it was $X \rightarrow ab$, and then $S=>^{i+1} a^{k+1}b^{k+1}c^jYd^j$If last derivation was $Y \rightarrow cYd$, then  $j' = j+1$ and $S=>^{i+1} a^{k}Xb^{k}c^{j+1}Yd^{j+1}$Similar case if it was $Y \rightarrow cd$, and then $S=>^{i+1} a^{k}Xb^{k}c^{j+1}d^{j+1}$Since $L(G1)$ contains terminal words, the last derivations must be $X \rightarrow ab$ or $Y \rightarrow cd$. By that we proved that $L(G1) \subseteq \{ a^nb^nc^md^m | n,m > 0\}$