Derivation of Trees
The grammar implicitly defines a set of trees: any tree that can be derived from using the rule set is said to be described by . This set of trees is known as the language of . To express this more formally, we define the relation on the set as follows:
Wwe say that can be derived in a single step into a tree (in short: ), if there is a context and a production such that:
- , and
- .
Here, a context means a tree with exactly one hole in it; if is such a context, we denote by the result of filling the tree into the hole of .
The tree language generated by is the language .
Here, denotes the set of all trees composed from symbols of, while denotes successive applications of .
A language generated by some regular tree grammar is called a regular tree language.
Read more about this topic: Regular Tree Grammar
Famous quotes containing the word trees:
“Below me trees unnumbered rise,
Beautiful in various dyes:
The gloomy pine, the poplar blue,
The yellow beech, the sable yew,
The slender fir that taper grows,
The sturdy oak with broad-spread boughs.”
—John Dyer (16991758)