Derivation Tree definition application, approaches in CFG

A ‘derivation tree’ is an ordered tree in which the nodes are labeled with the left sides of productions and the children of a node represent its corresponding right sides. A derivation tree is the tree representation of the CFG (Context Free Grammar). It consists of three types of nodes;

• Root Nodes: It is a non terminal variable in the production of the grammar that exists at the left side of the production rules or root of the tree is represented by the start symbol of the Context free grammar (CFG) production rules.
• Intermediate Nodes: All variables accepts root node considered as the intermediate nodes. Except the start symbol of non-terminals in the production rules becomes the part of intermediate node.
• Leaves Nodes: Nodes having no childes considered as leaves. Each leaf node is represented by a terminal.

Note: Derivation tree is also called Parse Tree, Production Tree, Generation Tree as well.

Formal Definition of a Derivation Tree:

Let G = (V, T, S, P) be a CFG. An ordered tree is a derivation tree for G if and only if it has the following properties:

1. The root of the derivation tree is S.
2. Each and every leaf in the tree has a label from T ∪{ε}.
3. Each and every interior vertex (a vertex which is not a leaf) has a label from V.
4. If a vertex has label A∈ V, and its children are labeled (from left to right) a₁, a₂, .. .. .. .., a_n, then P must contain a production of the form
   A → a₁, a₂, .. .. .. .., a_n
5. A leaf labeled ε has no siblings, that is, a vertex with a child labeled ε can have no other children.

Application of Derivation Tree:

Derivation trees play a very important role in parsing theory and in the proof of a strong version of the pumping lemma for the context-free languages known as Ogden’s lemma.

Approaches of derivation tree:

There are two different approaches to draw a derivation tree:

1. Top-down Approach:

• Starts with the starting symbol S
• Goes down to tree leaves using productions

2. Bottom-up Approach:

• Starts from tree leaves i.e. terminals of the strings
• Proceeds upward to the root which is the starting symbol S

Sentential Form and Partial Derivation Tree:

A partial derivation tree is a sub-tree of a derivation tree/parse tree such that either all of its children are in the sub-tree or none of them are in the sub-tree.

Example:

If in any CFG the productions are:

S → AB
A → aaA | ε
B → Bb | ε

The partial derivation tree can be the following:

If a partial derivation tree contains the root S, it is called a sentential form. The above sub-tree is also in sentential form.