# How i can use Mathematical induction to prove CFG production? [duplicate]

If I have production $G_n$

$S \rightarrow A_i b_i \quad$ for $1 \le i \le n$

$A_i \rightarrow a_j A_i \mid a_j\quad$ for $1 \le i$ and $i \ne j$

1. Prove $G_n$ is sub-productions from $2n^2 - n$
2. Prove $G_n$ is $LR(0)$ production from $2^n + n^2 + n$

## marked as duplicate by Raphael♦Apr 14 '13 at 19:11

• I understand what the productions of $G_n$ are, but what do you mean by ‘sub-productions from $2n^2-n$’ and ‘$LR(0)$ production from $2^n+n^2+n$’? $G_n$ has $n$ productions of the first type and $n^2-n$ of the second type, so it has $2n^2-n$ productions altogether; if that’s what the first question asks you to prove, it does not require induction. – Brian M. Scott Jan 27 '13 at 21:27