Introduction: A ‘derivation tree’ is an ordered tree which the the nodes are labeled with the left sides of productions and in which the children of a node represent its corresponding right sides.
Definition of a Derivation Tree: Let G = (V, T, S, P) be a CFG. An ordered tree is a derivation tree for G iff it has the following properties:
Sentential Form: For a given CFG with productions S ® aA, A® aB, B® bB, B® a. The derivation tree is as shown below.
The resultant of the derivation tree is the word w = aaba. This is said to be in “Sentential Form”.
Partial Derivation Tree: In the definition of derivation tree given, if every leaf has a label from V ÈT È{l} it is said to be “partial derivation tree”.
Right Most/Left Most/Mixed Derivation
Consider the grammar G with production
Now, we have
The sequence followed is “left most derivation”, fol lowing “1121222”, giving “aababbb”.
The sequence 1212122 represents a “Mixed Derivation”, giving “aababbb”.
The sequence 1211222 represents a “Right Most Derivation”, giving “aababbb”.