# tree grammar

**tree grammar** 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.

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*)))))

#### More From encyclopedia.com

#### You Might Also Like

#### NEARBY TERMS

**tree grammar**