enter image description here

The above is a good visualization of a derivation for a specific sentence in a context free language. You can find many more on Google Images by searching "context free grammar."

Let's consider the language $\{a^nb^nc^n : n>0\}$ for which no CFG exists but a RCG does. What does the visualization for the parse structure of the sentence "aaaaabbbbbccccc" look like? You can draw the visualization in MS Paint: I don't care how ugly it is as long as it isn't confusing. But you must submit a picture for an answer.

  • 2
    $\begingroup$ The RCG grammar for $\{a^n b^n c^n \mid n > 0\}$ is $S(xyz) \to A(x,y,z)$, $A(ax,by,cz) \to A(x,y,z)$, $A(a,b,c) \to \epsilon$; so the diagram for $aaabbbccc$ is a "line" with nodes: $S(aaabbbccc) \to$ $A(aaa,bbb,ccc) \to $ $A(aa,bb,cc) \to$ $A(a,b,c) \to \epsilon$. $\endgroup$ Dec 30, 2017 at 1:33
  • $\begingroup$ Really? That's it? I was expecting something more. The tree branches of a context-free grammar tell me A LOT about its structure... but this tells me nothing. $\endgroup$ Jan 1, 2018 at 1:22

1 Answer 1


Edit: answer obeying the "spirit" of the question:

Let's use the rules $$S(xy)\to A(x,y)$$ $$A(x,ayb)\to A(x,x)A(y,y)$$ $$A(x,x)\to\epsilon$$ Then we can derive $S(aabb)\to A(a,abb)\to A(a,a)A(b,b)\to\epsilon$. In this case the parse tree is:

$$ \begin{eqnarray*} &S(aabb)\\ &\downarrow \\ &A(a,abb)\\ &\swarrow\quad\searrow \\ &A(a,a)\quad A(b,b)\\ &\searrow\quad\swarrow \\ &\epsilon\\ \end{eqnarray*} $$

Original answer obeying the "letter" of the question:

Using @MarzioDeBiasi's grammar $$\begin{eqnarray*}S(xyz)&{\color{red}\rightarrow}&A(x,y,z),\\ A(ax,by,cz)&{\color{green}\rightarrow}&A(x,y,z),\\ A(a,b,c)&{\color{blue}\rightarrow}&\epsilon,\end{eqnarray*}$$ the picture is:

$$\begin{eqnarray*} &S(aaaaabbbbbccccc)\\ &{\color{red}\downarrow}\\ &A(aaaaa,bbbbb,ccccc)\\ &{\color{green}\downarrow}\\ &A(aaaa,bbbb,cccc)\\ &{\color{green}\downarrow}\\ &A(aaa,bbb,ccc)\\ &{\color{green}\downarrow}\\ &A(aa,bb,cc)\\ &{\color{green}\downarrow}\\ &A(a,b,c)\\ &{\color{blue}\downarrow}\\ &\epsilon\end{eqnarray*}$$

  • $\begingroup$ Sorry, but this is not a visualization. The tree branches of a context-free grammar tell me A LOT about its structure... but this tells me nothing. There's nothing graphical here that gives me any insight about the structure of a RCG. Not trying to be rude. $\endgroup$ Jan 1, 2018 at 1:24
  • $\begingroup$ @TomislavOstojich I guess the problem is that the example $a^nb^nc^n$ is rather simple $\endgroup$ Jan 1, 2018 at 2:43
  • $\begingroup$ You're right. It is my fault for picking a simple example. However, I have a hard time thinking of "complex" RCGs, so if you can think of a more complex one and create a graph of that... I'll award you the bounty. The reason why I can't award you the bounty as it is is because your answers meets the letter of my criteria, but not the spirit of it ;) $\endgroup$ Jan 1, 2018 at 2:46
  • $\begingroup$ @TomislavOstojich OK fine... I've made a new example that's "non-linear" now :) $\endgroup$ Jan 2, 2018 at 6:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.