In my university's automata theory book it is claimed that the following two arithmetic grammars generate the same arithmetic language but no proof is shown.
$G_1=(\{E\}, \{a,+,*,(,)\}, \{E\to E+E|E*E|(E)|a\}, E)$ $G_2=(\{E, T, F\}, \{a,+,*,(,)\}, \{E\to E+T|T, T\to T*F|F, F\to (E)|a\}, E)$
(the first one is ambiguous and the second one is unambiguous)
I've tried to prove that $L(G_1)=L(G_2)$ (I.e. $L(G_1)\subseteq L(G_2)$ and $L(G_2)\subseteq L(G_1)$) but I got stuck since I do not really know which statement to prove by induction.
Also I am stuck at proving (by induction) that $L(G_1)=\mathscr{A}_{\infty}$ where $\mathscr{A}_\infty$ is the set of all arithmetic expressions defined as follows:
$\mathscr{A}_0 =\{a\}$.
$\forall n\in\mathbb{N}, \mathscr{A}_{n+1}=\mathscr{A}_n \cup \{ \alpha @ \beta| \alpha,\beta\in\mathscr{A}_n, @\in\{+,*\}\}\cup\{(\alpha)|\alpha\in\mathscr{A}_n\}$
$\mathscr{A}_\infty=\bigcup_{n\in\mathbb{N}}\mathscr{A}_n$
Thanks for any help or guideline.
One part of your puzzle comes from considering the set of strings that can be produced by a grammar by a derivation tree of fixed height. Let $S_i$ be the set of strings that $G_1$ can produce in a parse tree of height $i$.
$S_0 = S_1 = \varnothing$ and $S_2 = \left\{a\right\}$ by inspection.
For $i\ge 2$, $S_{i+1} = \left\{ \alpha@\beta ~|~ \alpha, \beta \in S_i, @ \in \left\{+,*\right\}\right\} \cup \left\{ (\alpha) ~|~ \alpha \in S_i \right\} \cup \left\{a\right\}$ as a direct translation of the rules of $G_1$.
$L(G_1) = {\displaystyle\bigcup_{n\in\mathbb{N}}}S_n$.
You should be able to show by induction that $S_i = {\displaystyle\bigcup_{0 \le j < i-1}}\mathscr{A}_j$, hence $L(G_1)=\mathscr{A}_{\infty}$. If you can similarly show $L(G_2)=\mathscr{A}_{\infty}$ then you're done.