# How do I use induction to show that the language of a grammar is contained in a given set? [duplicate]

This question already has an answer here:

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?

## marked as duplicate by Raphael♦Nov 10 '14 at 12:35

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

• Well in fact that's only part of the question. There are 3 other forms before that one. The first one I had no problem with as in the inductive case it did not contain power of the form n+2. Also I got stuck in the inductive case because I couldn't get from The inductive hypothesis to the required answer due to there being no non-terminal symbols. – user3148942 Nov 9 '14 at 10:38
• What is your inductive hypothesis? – Roi Divon Nov 9 '14 at 12:09
• $$S=> (a^k X b^K c^j Y d^j )$$ where n =k and m = j – user3148942 Nov 9 '14 at 13:35
• Try $S=>^i a^kXb^kc^jYd^j$ where $j,k < i$ as your induction hypothesis. Then in the inductive step, you have two cases of the $i+1$ deriviation – Roi Divon Nov 9 '14 at 15:16
• @RoiDivon Post as an answer? – Yuval Filmus Nov 10 '14 at 0:14

## 1 Answer

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\}$