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:
“One wonders that the tithing-men and fathers of the town are not out to see what the trees mean by their high colors and exuberance of spirits, fearing that some mischief is brewing. I do not see what the Puritans did at this season, when the maples blaze out in scarlet. They certainly could not have worshiped in groves then. Perhaps that is what they built meeting-houses and fenced them round with horse-sheds for.”
—Henry David Thoreau (1817–1862)