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:
“The sugar maple is remarkable for its clean ankle. The groves of these trees looked like vast forest sheds, their branches stopping short at a uniform height, four or five feet from the ground, like eaves, as if they had been trimmed by art, so that you could look under and through the whole grove with its leafy canopy, as under a tent whose curtain is raised.”
—Henry David Thoreau (1817–1862)