Generate the word using this grammar

Question

Using this grammar, over the alphabet $\Sigma=\{a\}$ $$ S \rightarrow a \\ S\rightarrow CD \\ C\rightarrow ACB \\ C\rightarrow AB \\ AB\rightarrow aBA \\ Aa\rightarrow aA \\ Ba\rightarrow aB \\ AD\rightarrow Da \\ BD\rightarrow Ea \\ BE\rightarrow Ea \\ E\rightarrow a \\ $$ Im trying to show that the working string $aaaaaaaaaBBBAAAD$ or $a^{n^2} B^nA^nD$ generates the word $a^{(n+1)^2}$

Answer 1

Start at the end! There is only one applicable production: #8. $D$ moves backward over the $A$'s turning them into $a$'s. Then use #9, and repeatedly #10.

Please take a piece of paper and count the $a$'s generated. Probably the expression $(n+1)^2 = n^2+2n+1$ is useful.

Answer 2

Firstly, let's see step by step a sequence of production usage in order to draw the general conclusion:
$$aaaaaaaaaBBBAA\mathbf{AD}\underset{prod8}{\rightarrow}~a...aBBBA\mathbf{AD}a\underset{prod8}{\rightarrow}~a...aBBB\mathbf{AD}aa\underset{prod8}{\rightarrow}$$ $$\underset{prod8}{\rightarrow}a...aBB\mathbf{BD}aaa\underset{prod9}{\rightarrow}a...aB\mathbf{BE}aaaa\underset{prod10}{\rightarrow}a...a\mathbf{BE}aaaaa\underset{prod10}{\rightarrow}$$ $$\underset{prod10}{\rightarrow}a...a\mathbf{E}aaaaaa\underset{prod11}{\rightarrow}a...a\boldsymbol{aaaaaaa}$$

Finally, we have 16 'a's in our word, which verifies the general formula: $a^{{(n+1)}^2}$.
I guess you have to prove it parametrically, not just show the application of the productions on the given string. So you could say that:

• n 'a's are generated by consuming the 'A's with the production #8, as we have 'D' repeated only once and combined with the 'A's before it we take "Da" n times.
• 1 'a' is generated by using the production #9 once, which consumes one 'B' at a time and replaces 'D' with 'E'.
• 2 'a's (or better n-1 'a's) are generated by using the production #10, which consumes one 'B' at a time.
• Finally, 1 'a' is generated, as E is consumed with production #11

To sum up, we have: $n^2$ 'a's from the given word, $n$ from the 1st step, $1+(n-1)=n$ from steps 2 & 3 and at last $1$ 'a'as described in step 4 $\Rightarrow n^2+2n+1=(n+1)^2$ 'a's.