Consider the family of grammars $G_n,~n\geq2$. $$S \rightarrow A_ib_i~,~for~~1\leq i \leq n$$ $$A_i \rightarrow a_jA_i~|~a_j~,~for~~1 \leq i,j \leq n~~and~~i \neq j$$
where multiple alternative right sides result from different values of $i,j$ while the terminal symbols $a_i$ and $b_i$ are not necessarily different from each other.
Show that $G_n$ has exactly $n*2^{n-1}+n^2+1$ sets of LR(0) items.
Examine if $G_n$ is LR(k) for some k.
The above exercise is similar to Exercise 4.6.7 (page 258) from the "Compilers: Principles, Techniques & Tools", 2nd Edition (a.k.a.Dragonbook) by Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman.
I gave it much thought and also read chapter 4 of the book that is about Syntax Analysis but I still can't figure out how to prove this. Especially for question 2. I have no clue how to draw a conclusion about if this family of grammars can be parsed by an LR(k) parser.
For part 1., I think it could be suitable to use induction to prove that this is the exact number of states for any $n \geq 2$. At first, you have to construct the LR(0) states for $G_2,~n = 2$ and prove that the states correspond to the formula we have to prove. And it happens that way, as there are 9 LR(0) states which means that $\Rightarrow n*2^{n-1}+n^2+1=2*2^{2-1}+2^2+1=4+4+1=9$. If it is helpful, I could post the state diagram for $n=2$. Also, I don't know if this would help, but I proved that the productions for any $n$ is exactly $2n^2-n$.
