Table of contents
1.
Introduction
2.
Derivation Tree and its properties
2.1.
Properties
2.2.
Types of Derivation Tree
3.
Example to understand Derivation Tree
3.1.
Examples on the left and Right Derivation Tree
3.1.1.
Left Derivation Tree
3.1.2.
Right Derivation Tree
4.
Frequently Asked Questions
4.1.
Why do we use a derivation tree?
4.2.
How many types of derivation trees are there? 
4.3.
What do you mean by CFG?
4.4.
What is Grammar in CFG?
5.
Conclusion
Last Updated: Mar 27, 2024

Derivation Tree

Author Naman Kukreja
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?
TOC

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

Example to understand Derivation Tree

Example 1: The production rules for the derivation tree are as follows:

E= E+E
E= E*E
E= a|b|c

And the input string is a*b+c

Step 1:

Step 1

Step 2:

Step 2

Step 3:

Step 3

Step 4:

Step 4

Step 5:

Step 5

 

Example 2

Now, we can make a derivation tree directly in one step.

S-> bSb |a| b

The given input string is bab.

So the derivation tree of the above problem will be as follows:

Derivation Tree

Also read, Arden's theorem

Examples on the left and Right Derivation Tree

Here, we will discuss the same example from both the left and right derivation tree method:

Example 3: 

S-> aAS|aSS
A->SbA|ba

And the input string is given as aabaa.

Left Derivation Tree

Left Derivation Tree

Right Derivation Tree

Right Derivation Tree

Check out this problem - XOR Queries On Tree

Frequently Asked Questions

Why do we use a derivation tree?

We use a derivation tree to show the derivation process of some production rules into the given string.

How many types of derivation trees are there? 

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

What do you mean by CFG?

CFG refers to Context-Free Grammar.

What is Grammar in CFG?

It is an entity that generates language.

Conclusion

In this blog, we have learned about  Derivation trees in CFG, their syntax, properties, and types, and these examples to understand them better.

Recommended Readings:


Check out some of the amazing Guided Paths on topics such as Data Structure and Algorithms, Aptitude Preparation, Competitive Programming, Basics of C, Basics of Java, etc. along with some Contests and Interview Experiences only on Coding Ninjas Studio

Live masterclass