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
Ipoh , Ipoh •capo • Gestapo •Aleppo, depot •downtempo, tempo, uptempo •Expo •cheapo, Ipoh, peep-bo, repo •hippo •hypo, typo •oppo, topo, troppo •compo • Lim… Bo Tree , Bo tree (Bodhi tree) In Buddhism, the pipal under which the Buddha (Siddhartha Gautama) found enlightenment (bodhi) at Bodh Gaya, near Varanasi, n In… beech , beech / bēch/ • n. (also beech tree) a large tree (genera Fagus and Notofagus) with smooth gray bark, glossy leaves, and hard, pale, fine-grained tim… calabash , cal·a·bash / ˈkaləˌbash/ • n. (also calabash tree) an evergreen tropical American tree (Crescentia cujete, family Bignoniaceae) that bears fruit in t… inverse , inverse
1. (converse) of a binary relation R. A derived relation R–1 such that whenever x R y then y R–1 x
where x and y are arbitrary elements of th… Monkey-puzzle Tree , monkey-puzzle tree
monkey-puzzle tree, evergreen tree (Araucaria araucana) native to Chile and widely cultivated elsewhere as an ornamental. The symm…
You Might Also Like
NEARBY TERMS
tree grammar