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(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)))))
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)))))
More From encyclopedia.com
You Might Also Like
NEARBY TERMS
tree grammar