<p>The Context-Free tree grammar has rules of the form:</p>

<p>$A\rightarrow t$ or $A(x_1,\dots,x_n)\rightarrow t_x$, </p>

<p>where $A\in N$, $t\in T(N\cup T)$, $t_x\in T(N\cup T\cup \{x_1,\dots,x_n\})$, $T(Z)$ means a set of all possible trees with labels from $Z$.</p>

<p>where $N$ is a finite unranked set of non-terminals and $T$ is a finite unranked set of terminals, $x_i$ are free-variables.</p>

<p>It is clear, that this form of rules is definitely <em>context-free</em>. </p>

<p>The thing which I doubt about is: would the following form of rules</p>

<p>$x_1(A)\rightarrow x_1(A_1,\dots,A_2)$, where $A_i\in(N\cup T)$,</p>

<p>be context-free? </p>

<p>(More generally: $x_1(A)\rightarrow x_1(t_1,\dots,t_2)$, where $t_i\in T(N\cup T)$).</p>

<p>(Obviously it is not context-free according to the definition, but why not?). I don't see any context here. Such kind of rules may be useful for describing changing of the branch without growing tree down. $X$ here is a free-variable, and it points to the arbitrary parent node of the terminal $A$.</p>

<p>The only one theoretical objection here against "context-free-ness" of this form of rules, is that this kind of rules implies, that non-terminal $A$ is not a root of the current derivation tree. From other hand, conventional rules of the form $A(X_1)\rightarrow\dots$ can not be applied for the case when $A$ is a leave in the current derivation.</p>

<p><strong>UPD</strong>: For those who asked me for an example of Context-free tree grammar, please refer this link: <a href="http://research.nii.ac.jp/~kanazawa/Courses/2011/Kyoto/cft.pdf" rel="nofollow noreferrer">http://research.nii.ac.jp/~kanazawa/Courses/2011/Kyoto/cft.pdf</a></p>

<p>Though it describes CFTG for <strong>ranked</strong> trees, obviously the same rules in the same semantics can be applied for the case of <em>unranked</em> trees.</p>

CC BY-SA 3.0
2017-11-27T17:50:38.857Z
@BjørnKjos-Hanssen See my update and this link: https://pdfs.semanticscholar.org/95a3/cb63b80c3416879d534f41eedcd174b40159.pdf .
Andrey Lebedev
CC BY-SA 3.0
2017-11-27T17:50:53.700Z
@BjørnKjos-Hanssen Please also be aware that I am considering case of unranked trees.
Andrey Lebedev
CC BY-SA 3.0
2017-11-30T13:35:56.960Z
What's the difference between the proposed rules $x(A)\to x(t_1,\dots,t_n)$, and simply having $A\to t_1,\dots,t_n$?
Sylvain
CC BY-SA 3.0
2017-11-30T13:37:03.293Z
@Sylvain what is this form $A\rightarrow t_1,\dots,t_n$? What is the right-hand side of this rule?
Andrey Lebedev
CC BY-SA 3.0
2017-11-30T13:39:06.277Z
If it is just a substitution of the non-terminal, then there is no difference. But such kind of rules aren't part of a standard rules definition for the CF tree grammars, are they?
Andrey Lebedev
CC BY-SA 3.0
2017-12-01T08:31:54.407Z
an issue is that you have not really defined CFTGs on `unranked' trees; that form of rules would probably be OK for them.  A syntax for CFTGs on unranked trees could be adapted from that of MTTs on unranked trees in Perst & Seidl, 2004 (https://doi.org/10.1016/j.ipl.2003.05.001).
Sylvain
<fl.formal-languages><tree><grammars><context-free>
"Context" understanding in tree grammars
Andrey Lebedev
# "Context" understanding in tree grammars

(Asked by: username_0 on 2017-11-20)

The Context-Free tree grammar has rules of the form:

$A\rightarrow t$ or $A(x\_1,\dots,x\_n)\rightarrow t\_x$,

where $A\in N$, $t\in T(N\cup T)$, $t\_x\in T(N\cup T\cup \{x\_1,\dots,x\_n\})$, $T(Z)$ means a set of all possible trees with labels from $Z$.

where $N$ is a finite unranked set of non-terminals and $T$ is a finite unranked set of terminals, $x\_i$ are free-variables.

It is clear, that this form of rules is definitely *context-free*.

The thing which I doubt about is: would the following form of rules

$x\_1(A)\rightarrow x\_1(A\_1,\dots,A\_2)$, where $A\_i\in(N\cup T)$,

be context-free?

(More generally: $x\_1(A)\rightarrow x\_1(t\_1,\dots,t\_2)$, where $t\_i\in T(N\cup T)$).

(Obviously it is not context-free according to the definition, but why not?). I don't see any context here. Such kind of rules may be useful for describing changing of the branch without growing tree down. $X$ here is a free-variable, and it points to the arbitrary parent node of the terminal $A$.

The only one theoretical objection here against "context-free-ness" of this form of rules, is that this kind of rules implies, that non-terminal $A$ is not a root of the current derivation tree. From other hand, conventional rules of the form $A(X\_1)\rightarrow\dots$ can not be applied for the case when $A$ is a leave in the current derivation.

**UPD**: For those who asked me for an example of Context-free tree grammar, please refer this link: <http://research.nii.ac.jp/~kanazawa/Courses/2011/Kyoto/cft.pdf>

Though it describes CFTG for **ranked** trees, obviously the same rules in the same semantics can be applied for the case of *unranked* trees.

**Tags:** fl.formal-languages, tree, grammars, context-free
> **Comments:**
> **username_0**: @BjørnKjos-Hanssen See my update and this link: https://pdfs.semanticscholar.org/95a3/cb63b80c3416879d534f41eedcd174b40159.pdf .  
> **username_0**: @BjørnKjos-Hanssen Please also be aware that I am considering case of unranked trees.  
> **username_1**: What's the difference between the proposed rules $x(A)\to x(t_1,\dots,t_n)$, and simply having $A\to t_1,\dots,t_n$?  
> **username_0**: @Sylvain what is this form $A\rightarrow t_1,\dots,t_n$? What is the right-hand side of this rule?  
> **username_0**: If it is just a substitution of the non-terminal, then there is no difference. But such kind of rules aren't part of a standard rules definition for the CF tree grammars, are they?  
> **username_1**: an issue is that you have not really defined CFTGs on `unranked' trees; that form of rules would probably be OK for them.  A syntax for CFTGs on unranked trees could be adapted from that of MTTs on unranked trees in Perst & Seidl, 2004 (https://doi.org/10.1016/j.ipl.2003.05.001).  

---

## 0 answers

