## Quick Reference

A generalization of the notion of grammar, applying to trees (often called **terms** in this context) rather than strings (see tree language). A regular tree grammar is the corresponding generalization of the notion of regular grammar. Productions have the form *A* → *t*, 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.

*A* → *t*,

*S* → *h*(*a*,*g*(*S*),*b*) | *c*

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*(*x*_{1},*x*_{2}) → *f*(*x*_{2},*F*(*x*_{1},*g*(*x*_{2}))) | *h*(*x*_{1},*x*_{1},*x*_{2}) 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*)))))

*F*(*x*_{1},*x*_{2}) →

*f*(*x*_{2},*F*(*x*_{1},*g*(*x*_{2}))) | *h*(*x*_{1},*x*_{1},*x*_{2})

*f*(*b*,*F*(*a*,*g*(*b*))),

*f*(*b,f*(*g*(*b*),*F*(*a,g*(*g*(*b*))))),

*f*(*b,f*(*g*(*b*),*h*(*a*,*a*,*g*(*g*(*b*)))))

**Tree grammar.**Language generated by a tree grammar

**From:**
tree grammar
in
A Dictionary of Computing »

*Subjects:*
Computing.

## Related content in Oxford Index

##### Reference entries

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.