derivation tree of a derivation
Constructing a Derivation from a Derivation Tree
Let $G$ be a contextfree grammar. Given a (finite) derivation tree $T$ of $G$, we can construct a derivation $D$ of $G$. There are two ways of doing this: topdown, or bottomup.
The idea with the topdown 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 topdown 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\ge 0$, and ${Y}_{i}=\{{n}_{1},\mathrm{\dots},{n}_{k}\}$ with $$. It is easy to see that ${D}_{i}$ is the derivation $\sigma {\Rightarrow}^{*}[{n}_{1}]\mathrm{\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},\mathrm{\dots},{n}_{m}^{\prime}$ such that $$. Then set

–
${X}_{i+1}:={X}_{i}\cup \{{n}_{j}\}$,

–
${Y}_{i+1}:=({Y}_{i}\{{n}_{j}\})\cup \{{n}_{1}^{\prime},\mathrm{\dots},{n}_{m}^{\prime}\}$, and

–
${D}_{i+1}:={D}_{i}\Rightarrow [{n}_{1}]\mathrm{\cdots}[{n}_{j1}][{n}_{1}^{\prime}]\mathrm{\cdots}[{n}_{m}^{\prime}][{n}_{j+1}]\mathrm{\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 topdown.
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 bottomup 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}=\mathrm{\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 topdown iff it can be constructed from the bottomup.
Constructing a Derivation Tree from a Derivation
Conversely, given a derivation $D=\sigma \Rightarrow {W}_{1}\Rightarrow \mathrm{\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)

(a)
Set node $(1)$ whose label is $\sigma $.

(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},\mathrm{\dots},{p}_{m})$ is the node whose label is $P$.

*
If $Q={N}_{1}\mathrm{\cdots}{N}_{k}$, where each ${N}_{j}\in \mathrm{\Sigma}$, then define nodes
$$({p}_{1},\mathrm{\dots},{p}_{m},1),\mathrm{\dots},({p}_{1},\mathrm{\dots},{p}_{m},k)$$ whose labels are ${N}_{1},\mathrm{\dots},{N}_{k}$ respectively.

*
If $Q=\lambda $, then define one node $({p}_{1},\mathrm{\dots},{p}_{m},1)$ whose label is $\lambda $.

*

(c)
Continue (b) until nodes whose labels are symbols forming word ${W}_{n}$ are defined.

(a)

2.
Defining arrows: Given two nodes $p=({p}_{1},\mathrm{\dots},{p}_{r})$ and $q=({q}_{1},\mathrm{\dots},{q}_{s})$, an arrow is constructed from $p$ to $q$ iff $s=r+1$ and ${p}_{1}={q}_{1},\mathrm{\dots},{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. PrenticeHall, 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, AddisonWesley, (1969).
Title  derivation tree of a derivation 

Canonical name  DerivationTreeOfADerivation 
Date of creation  20130322 19:00:25 
Last modified on  20130322 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 