derivation tree of a derivation

Constructing a Derivation from a Derivation Tree

Let $G$ be a context-free grammar. Given a (finite) derivation tree $T$ of $G$ , we can construct a derivation $D$ of $G$ . There are two ways of doing this: top-down, or bottom-up.

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 $n$ of $T$ , denote $[n]$ the label of $n$ .

The top-down approach works as follows:

1.

Set $X_{0}=Y_{0}=:\{r\}$ , and $D_{0}$ the derivation $\sigma=[r]$ , where $r$ is the root of $T$ .
2.

Suppose $X_{i},Y_{i}$ and $D_{i}$ are defined for $i\geq 0$ , and $Y_{i}=\{n_{1},\ldots,n_{k}\}$ with $n_{1}<\cdots<n_{k}$ . It is easy to see that $D_{i}$ is the derivation $\sigma\Rightarrow^{*}[n_{1}]\cdots[n_{k}]$ .
If none of the elements of $Y$ have children, then set $D:=D_{i}$ . Otherwise, pick a node $n_{j}\in Y_{i}$ with children $n_{1}^{\prime},\ldots,n_{m}^{\prime}$ such that $n_{1}^{\prime}<\cdots<n_{m}^{\prime}$ . Then set
- –
  
  $X_{i+1}:=X_{i}\cup\{n_{j}\}$ ,
- –
  
  $Y_{i+1}:=(Y_{i}-\{n_{j}\})\cup\{n_{1}^{\prime},\ldots,n_{m}^{\prime}\}$ , and
- –
  
  $D_{i+1}:=D_{i}\Rightarrow[n_{1}]\cdots[n_{j-1}][n_{1}^{\prime}]\cdots[n_{m}^{% \prime}][n_{j+1}]\cdots[n_{k}]$ .

Since $T$ is finite, $D$ can be constructed in a finite number of steps above.

Definition. A derivation tree $T$ is said to correspond to a derivation $D$ if $D$ can be constructed from $T$ 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 $T$ corresponds to a unique leftmost derivation (written $LD(T)$ ) as well as a unique rightmost derivation (written $RD(T)$ ).

The bottom-up approach starts out with the result $u$ of the derivation tree $T$ . The result corresponds to leaves of $T$ . 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 $B$ of leaves, and form a new word $u_{1}$ from $u$ by replacing the labels of leaves in $B$ by the label of their parent. Then $u_{1}\Rightarrow u$ is a derivation step. Next, form a new tree $T_{1}$ from $T$ by removing the leaves of $T$ in $B$ . So $u_{1}$ is now the result of $T_{1}$ . Repeat the process just described, until all of the nodes are removed ( $T_{i}=\varnothing$ for some $i$ ), which is possible since $T$ is finite. What we end up with is a derivation. We will leave the formal detail to the reader.

Proposition 1.

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 $D=\sigma\Rightarrow W_{1}\Rightarrow\cdots\Rightarrow W_{n}$ , one can construct a derivation tree $T$ such that $D$ corresponds to $T$ . The way this works is as follows: start with the tree with a single node whose label is $\sigma$ . 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 $D$ corresponds to. This construction can be formalized as follows:

1.
Defining nodes: (The nodes of the tree $T$ will be tuples of positive integers)
1. (a)
  
  Set node $(1)$ whose label is $\sigma$ .
2. (b)
  Suppose nodes are defined for symbols occurring in $W_{i}$ . Look at the derivation step $W_{i}\Rightarrow W_{i+1}$ . Suppose it is based on production $P\to Q$ , and $(p_{1},\ldots,p_{m})$ is the node whose label is $P$ .
  - *
    
    If $Q=N_{1}\cdots N_{k}$ , where each $N_{j}\in\Sigma$ , then define nodes
    
    $(p_{1},\ldots,p_{m},1),\ldots,(p_{1},\ldots,p_{m},k)$
    
    whose labels are $N_{1},\ldots,N_{k}$ respectively.
  - *
    
    If $Q=\lambda$ , then define one node $(p_{1},\ldots,p_{m},1)$ whose label is $\lambda$ .
3. (c)
  
  Continue (b) until nodes whose labels are symbols forming word $W_{n}$ are defined.
2.

Defining arrows: Given two nodes $p=(p_{1},\ldots,p_{r})$ and $q=(q_{1},\ldots,q_{s})$ , an arrow is constructed from $p$ to $q$ iff $s=r+1$ and $p_{1}=q_{1},\ldots,p_{r}=q_{r}$ .
3.

Extending the partial order on $T$ to a linear order based on the nodes: see the entry on ordered tree for detail.

The algorithm shows that the derivation tree is uniquely constructed.

Definition. Given a derivation $D$ , the derivation tree of $D$ , denoted by $T_{D}$ , is the ordered tree constructed above from $D$ .

It is easy to see that $T_{D}$ corresponds to $D$ .

Remark. Suppose $u$ is a word derived by a derivation $D$ . One can find the leftmost derivation $D^{\prime}$ of $u$ using the methods provided above: first find $T_{D}$ of $D$ , then find $LD(T_{D})$ , and set $D^{\prime}=LD(T_{D})$ .

References

1 H.R. Lewis, C.H. Papadimitriou, Elements of the Theory of Computation. Prentice-Hall, Englewood Cliffs, New Jersey (1981).
2 A. Salomaa, Formal Languages, Academic Press, New York (1973).
3 J.E. Hopcroft, J.D. Ullman, Formal Languages and Their Relation to Automata, Addison-Wesley, (1969).

Title	derivation tree of a derivation
Canonical name	DerivationTreeOfADerivation
Date of creation	2013-03-22 19:00:25
Last modified on	2013-03-22 19:00:25
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	9
Author	CWoo (3771)
Entry type	Definition
Classification	msc 68Q42
Classification	msc 68Q45