Regular Tree Grammar - Derivation of Trees

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:

    I do not know but it is too much to read one newspaper a week. I have tried it recently, and for so long it seems to me that I have not dwelt in my native region. The sun, the clouds, the snow, the trees say not so much to me. You cannot serve two masters.
    Henry David Thoreau (1817–1862)