Derivation tree gives a way to show how a string can be derived from context free grammar. It is also called as parse tree, production tree, and syntax tree. The interior nodes of derivation tree are labeled with variables and leaves of this tree are labeled with terminals. We can also say that left-hand side of production rules is always interior nodes, and the right-hand side of production rules may be exterior nodes. The root of the derivation tree is labeled with start symbol or variable.
Formal Definitions of Derivation Tree
We can define a derivation tree of context free grammar G = (V, T, P, S). A derivation tree satisfies the following properties:
Types of Derivation Tree
Left Most Derivation Tree:
In left most derivation tree, for each step, production rule is applied to the leftmost variable that’s why it is called left most derivation tree.
Example:
Consider the Context Free Grammar:
S -> S * S
S -> S + S
S -> 0
S -> 1
S -> 2
Find string 0 + 1 * 2
Solution:
Let us derive string 0 + 1 * 2 using left most derivation.
S => S * S
=> 0 + S
=> 0 + S * S
=> 0 + 1 * S
=> 0 + 1 * 2
In this, each step of derivation, the production rule is applied to leftmost variable.
Right Most Derivation Tree:
In right most derivation tree each step, production rule is applied to the rightmost variable that’s why it is called right most derivation tree
Example:
Consider the Context Free Grammar:
S -> S * S
S -> S + S
S -> 0
S -> 1
S -> 2
Find string 0 + 1 * 2
Solution:
Let us derive string 0 + 1 * 2 using left most derivation.
S => S + S
=> S + S * S
=> S + S * 2
=> S + 1 * 2
=> 0 + 1 * 2
In this, for each step of derivation the production rule is applied to rightmost variable
Mixed Derivation Tree:
In a derivation, if the production rule is not applied to left most variable in each step or right most variable in each step, then it is called mixed derivation.
Example:
Consider the Context Free Grammar:
S -> S * S
S -> S + S
S -> 0
S -> 1
S -> 2
Find string 0 + 1 * 2
Solution:
Let us derive string 0 + 1 * 2
S => S + S
=> S + S * S
=> 0 + S * S
=> 0 + S * 2
=> 0 + 1 * 2
In each step of derivation, the production rule is applied to both leftmost and rightmost variable.
Let us take some examples of derivation tree
Example:
Consider the context free grammar G = (V, T, P, S)
Where,
S -> 0S1
V = {E, T, F}
T = {a, +,*, (,)}
S is the start symbol.
P is the set of production rules in context free grammar, which are defined as follows:
E -> E + T | T | a
T -> T * F | F | a
F -> (E) | a
Find derivation of string a + a * a
Solution:
Let us see derivation of string a + a * a
E => E + T
=> E + T * F
=> a + T * F
=> a + a* F
=> a + a* a
The derivation for string a + a * a is shown below: