Derivation Tree

Introduction

Whenever you have given a string and some production links in Context-Free Grammar, you face problems understanding the process behind converting those rules into the given string. Then what should you do?

The answer is you can use the derivation tree. They will provide you with a step-by-step crystal clear idea with a proper explanation of the processes of converting these rules and statements into the given string. 

So without wasting any further time, let's directly move to our topic.

Also see, Turing Machine in TOC.

Derivation Tree and its properties

You can understand the derivation tree in context-free grammar as the graphical representation for the derivation of the production rules.

It is used to show how you can derivate from some string with a given set of production rules. Sometimes derivation tree is also referred to as the parse tree.

The parse tree or derivation tree follows the precedence of operations.

The deepest subtree should be traversed first. So the operator in the subtree has more precedence over the operator in the parent node.

Read About - Simplification of CFG

Properties

The derivation tree follows some properties, which are stated as follows:

1. The start symbols are always indicated by the root node.
2. The leaf node will be the terminal node.
3. The derivation is read from left to right.
4. The interior nodes are always non-terminal nodes.

Types of Derivation Tree

There are mainly two types of derivation trees: left derivation tree and right derivation tree.

1. Left Derivation Tree: A left Derivation Tree is obtained by applying production to the leftmost variable in each step.
2. Right Derivation Tree: A right Derivation Tree is obtained by applying production to the rightmost variable in each step.

Read About - Moore Machine