# Regarding proper form of production rules of Context-free tree grammars

Is it possible to describe Context-free Tree Grammar $G_t$ such that set of yields of its trees will coincide with Context-sensitive word language $a^nb^nc^n$?

$\{a^nb^nc^n | n>0\}=\{Yield(t)|t\in L(G_t)\}$

I've tried to do it, using commonly used definition of CFTG (for instance see here), but I failed to express proper context-sensitive rules, using rules of the form $A(x_1,\dots,x_n)\rightarrow\alpha$. Looks like its description power is not enough, as I we can not operate subtrees structure in left side of the rule.

This question induced by well-known obvious relation between Regular Tree Grammars and Context-free word languages.

I would be happy if somebody would build such CFTG or confirm my assumption, that it is simply not possible.

UPD: More specifically, the problem is definition of variables inside rules: $A(x_1,\dots,x_n)\rightarrow\alpha$. It seems to be quite blur, as it is not quite clear: what are these variables? Can we say, that $x_i\in T_{\Sigma\cup X_n}$, where $X_n=\{x_1,\dots,x_n\}$, or not?

If we can describe CFTG rule as: $A(f(x))\rightarrow A_t(a, A(x))$, then problem goes away, it solves the question. But would it satisfy CFTG definition?

• It's not possible, CFTG generate indexed languages as yield languages (en.wikipedia.org/wiki/Indexed_language), a strict subclass of CSL. – Sylvain Jan 23 '17 at 6:44
• The essential question is: can we use such kind of rules as $A(f(x))\rightarrow A_t(a, A(x))$ or not. – Andrey Lebedev Jan 23 '17 at 22:01
• @Sylvain, it looks like I'm confused now. The language $a^nb^nc^n$ is actually indexed language, hence it should be possible describe corresponsing CFTG – Andrey Lebedev Jan 23 '17 at 22:02
• seems like I read your question too fast: I thought you were asking whether CFTGs can generate any CSL. For the particular language $\{a^nb^nc^n\mid n>0\}$ you mention at the beginning of your question, it's the very first example in Fischer's paper (Grammars with macro-like productions. In SWAT’68, pages 131–142. dx.doi.org/10.1109/SWAT.1968.12.) – Sylvain Jan 24 '17 at 18:35

After a couple of hours of thinking I found at least proper form of grammar. Thanks to @Sylvain's commentary and link to Fisher's paper, which given me a clue.

Proper context-free tree grammar, which yield language coincides with $\{a^nb^nc^n|n>0\}$ will have simplest form:

$G=\{\Sigma,N,S,P\}$, where $\Sigma=\{a,b,c\}$, $N=\{S_t,F,A,B,C\}$, $S=\{S_t\}$, and set of production rules:

$S_t\rightarrow F(a,b,c)\\ F(x_1,x_2,x_3)\rightarrow F(A(a,x_1),B(b,x_2),C(c,x_3))$

That is it. Core idea is to wrap "stack" into subtrees of the form $A(a,x_1)$.

1. $S_t\Rightarrow F(a,b,c)$, $yield(F(a,b,c))=abc$
2. $S_t\Rightarrow F(a,b,c)\Rightarrow F(A(a,a),B(b,b),C(c,c))$, $yield(F(A(a,a),B(b,b),C(c,c)))=aabbcc$
3. $S_t\Rightarrow F(a,b,c)\Rightarrow F(A(a,a),B(b,b),C(c,c))\Rightarrow F(A(a,A(a,a)),B(b,B(b,b)),C(c,C(c,c)))$,