# Visualizing the parse structure of a range concatenation grammar

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.

• 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$. – Marzio De Biasi Dec 30 '17 at 1:33
• 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. – FloatingFoundation92 Jan 1 '18 at 1:22

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

• 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. – FloatingFoundation92 Jan 1 '18 at 1:24
• @TomislavOstojich I guess the problem is that the example $a^nb^nc^n$ is rather simple – Bjørn Kjos-Hanssen Jan 1 '18 at 2:43
• 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 ;) – FloatingFoundation92 Jan 1 '18 at 2:46
• @TomislavOstojich OK fine... I've made a new example that's "non-linear" now :) – Bjørn Kjos-Hanssen Jan 2 '18 at 6:45