You are here
Homederivation tree of a derivation
Primary tabs
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\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_{{j1}}][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 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}=\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\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},\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$.

(c) Continue (b) until nodes whose labels are symbols forming word $W_{n}$ are defined.
2. 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).
Mathematics Subject Classification
68Q42 no label found68Q45 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections