Introduction to Derivation
Grammars generate languages by repeatedly modifying given strings. Each modification of a string is in accordance with some production rules of the grammar.
In the theory of computation, Derivation is the process of deriving or generating a language from the given production rules. In this, the non-terminal is replaced by the corresponding strings of the right-hand side (RHS) of the production. But if there is more than one non-terminal, then which should be replaced first must be determined by derivation.
Depending on this selection, the derivation is divided into two parts:
Leftmost derivation: A derivation is called a leftmost derivation if we replace only the leftmost non-terminal by some production rule at each step of the generating process of the language from the grammar. | Rightmost derivation: A derivation is called a rightmost derivation if we replace only the rightmost non-terminal by some production rule at each step of the generating process of the language from the grammar. |
Example to understand the derivation
Construct the string 0100110 from the following grammar by using
i) Leftmost derivation ii) Rightmost derivation
S → 0S/1AA
A → 0/1A/0B
B → 1/0BB
Solution:
i) Leftmost Derivation
S → 0S → 01AA → 010BA → 0100BBA → 01001BA → 010011A → 0100110
(The non-terminals that are replaced are represented in red.)
ii) Rightmost Derivation
S → 0S → 01AA → 01A0 → 010B0 → 0100BB0 → 0100B10 → 0100110
(The non-terminals that are replaced are represented in red.)
Derivation Tree / Derivation Graph
The derivation is basically represented in the graphical form, which is also considered as Derivation graphs and popularly known as derivation trees or parses trees.
A ‘derivation tree’ is an ordered tree in which the nodes are labeled with the left side 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 on 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. There will only be one root node.
- Intermediate Nodes: All variables except the root node are considered as intermediate nodes. But each node should have its predecessor as well as a successor. If it doesn’t have a predecessor then it will be the root node and if no successor then it will leave the node. Except for the start symbol of non-terminals in production, the rules become part of the intermediate node.
- Leaves Nodes: Nodes with no child are considered leaves. Each leaf node is represented by a terminal.
Note: Derivation trees are also called Parse Tree, Production Tree, and 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:
- The root of the derivation tree is S.
- Each and every leaf in the tree has a label from T ∪{ε}.
- Each and every interior vertex (a vertex that is not a leaf) has a label from V.
- If a vertex has label A∈ V, and its children are labeled (from left to right) a1, a2,…, an, then P must contain the production of the form A → a1, a2, .. .. .. .., an
- A leaf labeled ε has no siblings, that is, a vertex with a child labeled ε can have no other children.
Approaches of derivation tree:
There are two different approaches to drawing a derivation tree:
1. Top-down Approach:
It starts with the starting symbol S
Goes down to tree leaves using productions
2. Bottom-up Approach:
Starts with tree leaves i.e. terminals of the strings
Proceeds upward to the root which is the starting symbol S
