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

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

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

<p>$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))$</p>

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

<p>Thereby we receive following productions:</p>

<ol>
<li>$S_t\Rightarrow F(a,b,c)$, $yield(F(a,b,c))=abc$</li>
<li>$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$</li>
<li>$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)))$,</li>
<li>and so on.</li>
</ol>

CC BY-SA 3.0
2017-01-25T00:41:59.323Z
2017-01-25T01:00:20.997Z
2017-01-25T01:00:20.997Z
Andrey Lebedev
<p>Is it possible to describe Context-free <strong>Tree</strong> Grammar $G_t$ such that set of yields of its trees will coincide with Context-sensitive word language $a^nb^nc^n$? </p>

<p>$\{a^nb^nc^n | n&gt;0\}=\{Yield(t)|t\in L(G_t)\}$</p>

<p>I've tried to do it, using commonly used definition of CFTG (for instance see <a href="http://www.aclweb.org/anthology/C04-1012" rel="nofollow noreferrer">here</a>), 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.</p>

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

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

<p><strike>
<strong>UPD</strong>: 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?</p>

<p>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?
</strike></p>

CC BY-SA 3.0
2017-01-23T06:44:31.177Z
It's not possible, CFTG generate indexed languages as yield languages (https://en.wikipedia.org/wiki/Indexed_language), a strict subclass of CSL.
Sylvain
CC BY-SA 3.0
2017-01-23T22:01:29.197Z
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
CC BY-SA 3.0
2017-01-23T22:02:34.040Z
@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
CC BY-SA 3.0
2017-01-24T18:35:44.307Z
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.  http://dx.doi.org/10.1109/SWAT.1968.12.)
Sylvain
<fl.formal-languages><tree><grammars><context-free>
Regarding proper form of production rules of Context-free tree grammars
Andrey Lebedev
# Regarding proper form of production rules of Context-free tree grammars

(Asked by: username_0 on 2017-01-22)

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](http://www.aclweb.org/anthology/C04-1012)), 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?

**Tags:** fl.formal-languages, tree, grammars, context-free

> **Comments:**
> **username_1**: It's not possible, CFTG generate indexed languages as yield languages (https://en.wikipedia.org/wiki/Indexed_language), a strict subclass of CSL.  
> **username_0**: The essential question is: can we use such kind of rules as $A(f(x))\rightarrow A_t(a, A(x))$ or not.  
> **username_0**: @username_1, 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  
> **username_1**: 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.  http://dx.doi.org/10.1109/SWAT.1968.12.)  

---

## 1 answers

### Answer by username_0 on 2017-01-25. Score: 1 | Accepted answer

After a couple of hours of thinking I found at least proper form of grammar. Thanks to @username_1'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)$.

Thereby we receive following productions:

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)))$,
4. and so on.


---

