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

where A is a nonterminal and t a term, e.g.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.

This means, for example, that F(a,b) could be rewritten toand then toand then to