derivation tree
Given a formal grammar $G=(\mathrm{\Sigma},N,P,\sigma )$, recall that a derivation from words $u$ to $v$ over $\mathrm{\Sigma}$ can be visualized as a finite sequence^{} of words over $\mathrm{\Sigma}$, connected by the binary relation^{} $\Rightarrow $:
$${u}_{0}\Rightarrow {u}_{1}\Rightarrow \mathrm{\cdots}\Rightarrow {u}_{n}$$  (1) 
where $u={u}_{0}$ and $v={u}_{n}$. Each ${u}_{i}\Rightarrow {u}_{i+1}$ is a derivation step, which means that there is a production in $P$ which, when applied to ${u}_{i}$, yields ${u}_{i+1}$. In other words, there is $A\to B$ in $P$ such that ${u}_{i}=xAy$ and ${u}_{i+1}=xBy$, where $x,y$ are words over $\mathrm{\Sigma}$.
When the formal grammar $G$ is contextfree, a derivation can be represented by an ordered tree^{}, revealing the structure^{} behind the derivation that is usually not apparent in the linear representation $(1)$ above. This ordered tree is variously known as a derivation tree or a parse tree, depending how it is being used.
In the foregoing discussion, $G$ is contextfree, and any derivation of $G$ begins with $\sigma $, the starting nonterminal.
Definition. A parse tree of $G$ is an ordered tree $T$ such that

1.
the nodes of $T$ are labeled by elements of $\mathrm{\Sigma}$, or the empty word^{} $\lambda $,

2.
if a node with label $A$ has children ${N}_{1},\mathrm{\dots},{N}_{k}$ such that $$, and that each ${N}_{i}$ has label ${A}_{i}$, then $A\to {A}_{1}\mathrm{\cdots}{A}_{k}$ is a production of $P$.
A parse tree such that the root has label $\sigma $ is called a derivation tree, or a generation tree. Every subtree of a derivation tree is a parse tree.
Remark. Since $G$ is contextfree, in a parse tree, any node that is not a leaf is labeled by a nonterminal symbol.
For example, if $\mathrm{\Sigma}=\{\sigma ,a,b,X,Y\}$, $N=\{\sigma ,X,Y\}$, and the productions of $P$ are
$$\sigma \to aXY,X\to bYb,Y\to Xa,Y\to a,$$ 
then
represents a derivation tree of $G$. The tree represents the following derivations

•
$\sigma \Rightarrow aXY\Rightarrow abYbY\Rightarrow abXabY\Rightarrow abXabb$

•
$\sigma \Rightarrow aXY\Rightarrow abYbY\Rightarrow abYbb\Rightarrow abXabb$

•
$\sigma \Rightarrow aXY\Rightarrow aXb\Rightarrow abYbb\Rightarrow abXabb$
Definition. If ${\mathrm{\ell}}_{1},\mathrm{\dots},{\mathrm{\ell}}_{m}$ are the leaves of a parse tree $T$, with $$, then the result of $T$ is the word ${B}_{1}\mathrm{\cdots}{B}_{m}$, where ${B}_{i}\in \mathrm{\Sigma}$ is the label of ${\mathrm{\ell}}_{i}$. A word over $\mathrm{\Sigma}$ is said to correspond to a parse tree if it is the result of the tree.
In the example above, the result of the tree is $abXabb$.
Remark. A derivable word may correspond to several derivation trees. See the entry ambiguous grammar for more detail.
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 

Canonical name  DerivationTree 
Date of creation  20130322 19:00:17 
Last modified on  20130322 19:00:17 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  10 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 68Q42 
Classification  msc 68Q45 
Synonym  generation tree 
Defines  parse tree 
Defines  result of a derivation tree 