0
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 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$ – Marzio De Biasi Dec 30 '17 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$ – kakashi10192020 Jan 1 '18 at 1:22
2
+25
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\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$ – kakashi10192020 Jan 1 '18 at 1:24
  • $\begingroup$ @TomislavOstojich I guess the problem is that the example $a^nb^nc^n$ is rather simple $\endgroup$ – Bjørn Kjos-Hanssen♦ Jan 1 '18 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$ – kakashi10192020 Jan 1 '18 at 2:46
  • $\begingroup$ @TomislavOstojich OK fine... I've made a new example that's "non-linear" now :) $\endgroup$ – Bjørn Kjos-Hanssen♦ Jan 2 '18 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.