where A is a nonterminal and t a term, e.g. S → h(a,g(S),b) | c
These productions generate the regular tree language shown in the diagram. Note that the frontiers of these trees are the strings shown below each tree in the diagram. A set of strings is context-free if and only if it is the set of frontiers of the trees in a regular tree language.
The notion of context-free grammar can be similarly generalized. This time nonterminals can themselves be function symbols having an arbitrary number of arguments, e.g. F(x1,x2) → f(x2,F(x1,g(x2))) | h(x1,x1,x2)
This means, for example, that F(a,b) could be rewritten to f(b,F(a,g(b))),
and then to f(b,f(g(b),F(a,g(g(b))))),
and then to f(b,f(g(b),h(a,a,g(g(b)))))
"tree grammar." A Dictionary of Computing. . Encyclopedia.com. (August 19, 2018). http://www.encyclopedia.com/computing/dictionaries-thesauruses-pictures-and-press-releases/tree-grammar
"tree grammar." A Dictionary of Computing. . Retrieved August 19, 2018 from Encyclopedia.com: http://www.encyclopedia.com/computing/dictionaries-thesauruses-pictures-and-press-releases/tree-grammar