Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
Use any parsing algorithm? – Raphael Dec 4 '12 at 16:52
up vote 2 down vote accepted

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.

share|cite|improve this answer
ah, cheers, thanks for that – user3115 Dec 4 '12 at 1:32

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.