derivation tree of a derivation
Constructing a Derivation from a Derivation Tree
The idea with the top-down approach is to build the derivation one derivation step at a time, starting from the root of the tree. During each step, a node with children is picked so that the next derivation step is formed, thus creating a new derivation with the new derivation step attached. Do this until all nodes of the tree are used.
To facilitate the discussion, for each node of , denote the label of .
The top-down approach works as follows:
Set , and the derivation , where is the root of .
Suppose and are defined for , and with . It is easy to see that is the derivation .
If none of the elements of have children, then set . Otherwise, pick a node with children such that . Then set
Since is finite, can be constructed in a finite number of steps above.
Definition. A derivation tree is said to correspond to a derivation if can be constructed from from the top-down.
From the construction above, one sees that every derivation tree corresponds to at least one derivation. But it may correspond to more than one derivation. If, in the second step of the construction above, one always picks the smallest node with children in each step, then the corresponding derivation is the leftmost derivation. Similarly, consistently picking the largest node in each step results in the rightmost derivation. This shows that a derivation tree corresponds to a unique leftmost derivation (written ) as well as a unique rightmost derivation (written ).
The bottom-up approach starts out with the result of the derivation tree . The result corresponds to leaves of . Partition the set of leaves into blocks, so that two leaves belonging to the same block if they have the same parent. Pick a block of leaves, and form a new word from by replacing the labels of leaves in by the label of their parent. Then is a derivation step. Next, form a new tree from by removing the leaves of in . So is now the result of . Repeat the process just described, until all of the nodes are removed ( for some ), which is possible since is finite. What we end up with is a derivation. We will leave the formal detail to the reader.
A derivation can be constructed from the top-down iff it can be constructed from the bottom-up.
Constructing a Derivation Tree from a Derivation
Conversely, given a derivation , one can construct a derivation tree such that corresponds to . The way this works is as follows: start with the tree with a single node whose label is . At each derivation step, additional nodes are added from the tree constructed so far, until the last derivation step is processed. The tree so constructed has a natural linear ordering, and hence is a derivation tree, which corresponds to. This construction can be formalized as follows:
Defining nodes: (The nodes of the tree will be tuples of positive integers)
Set node whose label is .
Suppose nodes are defined for symbols occurring in . Look at the derivation step . Suppose it is based on production , and is the node whose label is .
If , where each , then define nodes
whose labels are respectively.
If , then define one node whose label is .
Continue (b) until nodes whose labels are symbols forming word are defined.
Defining arrows: Given two nodes and , an arrow is constructed from to iff and .
The algorithm shows that the derivation tree is uniquely constructed.
Definition. Given a derivation , the derivation tree of , denoted by , is the ordered tree constructed above from .
It is easy to see that corresponds to .
Remark. Suppose is a word derived by a derivation . One can find the leftmost derivation of using the methods provided above: first find of , then find , and set .
|Title||derivation tree of a derivation|
|Date of creation||2013-03-22 19:00:25|
|Last modified on||2013-03-22 19:00:25|
|Last modified by||CWoo (3771)|