<p><strong>Edit: answer obeying the "spirit" of the question:</strong></p>

<p>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:</p>

<blockquote>
  <p>$$
\begin{eqnarray*}
&amp;S(aabb)\\
&amp;\downarrow \\
&amp;A(a,abb)\\
&amp;\swarrow\quad\searrow \\
&amp;A(a,a)\quad A(b,b)\\
&amp;\searrow\quad\swarrow \\
&amp;\epsilon\\
\end{eqnarray*}
$$</p>
</blockquote>

<p><strong>Original answer obeying the "letter" of the question:</strong></p>

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

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

CC BY-SA 3.0
2018-01-01T01:24:40.313Z
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.
CosmicGenis
CC BY-SA 3.0
2018-01-01T02:43:06.557Z
@TomislavOstojich I guess the problem is that the example $a^nb^nc^n$ is rather simple
Bjørn Kjos-Hanssen
CC BY-SA 3.0
2018-01-01T02:46:32.967Z
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 ;)
CosmicGenis
CC BY-SA 3.0
2018-01-02T06:45:45.873Z
@TomislavOstojich OK fine... I've made a new example that's "non-linear" now :)
Bjørn Kjos-Hanssen
CC BY-SA 3.0
2017-12-30T06:27:56.237Z
2018-01-02T06:43:56.093Z
2018-01-02T06:43:56.093Z
Bjørn Kjos-Hanssen
<p><a href="https://i.sstatic.net/w8H6K.gif" rel="nofollow noreferrer"><img src="https://i.sstatic.net/w8H6K.gif" alt="enter image description here"></a></p>

<p>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."</p>

<p>Let's consider the language $\{a^nb^nc^n : n&gt;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.</p>

CC BY-SA 3.0
2017-12-30T01:33:18.313Z
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
CC BY-SA 3.0
2018-01-01T01:22:56.447Z
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.
CosmicGenis
<fl.formal-languages>
Visualizing the parse structure of a range concatenation grammar
CosmicGenis
# Visualizing the parse structure of a range concatenation grammar

(Asked by: username_0 on 2017-12-27)

[![enter image description here](https://i.sstatic.net/w8H6K.gif)](https://i.sstatic.net/w8H6K.gif)

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.

**Tags:** fl.formal-languages
> **Comments:**
> **username_1**: 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$.  
> **username_0**: 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.  

---

## 1 answers

### Answer by username_2 on 2017-12-30. Score: 2 | Accepted answer

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

> **Comments:**
> **username_0**: 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.  
> **username_2**: @TomislavOstojich I guess the problem is that the example $a^nb^nc^n$ is rather simple  
> **username_0**: 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 ;)  
> **username_2**: @TomislavOstojich OK fine... I've made a new example that's "non-linear" now :)  

---

