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.

  • $\begingroup$ @BjørnKjos-Hanssen See my update and this link: pdfs.semanticscholar.org/95a3/… . $\endgroup$ Nov 27, 2017 at 17:50
  • $\begingroup$ @BjørnKjos-Hanssen Please also be aware that I am considering case of unranked trees. $\endgroup$ Nov 27, 2017 at 17:50
  • $\begingroup$ 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$? $\endgroup$
    – Sylvain
    Nov 30, 2017 at 13:35
  • $\begingroup$ @Sylvain what is this form $A\rightarrow t_1,\dots,t_n$? What is the right-hand side of this rule? $\endgroup$ Nov 30, 2017 at 13:37
  • $\begingroup$ 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? $\endgroup$ Nov 30, 2017 at 13:39


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.