Left and Right Most Derivation Tree

In this class, We discuss the Left and Right Most Derivation Tree.

For Complete YouTube Video: Click Here

The reader should have prior knowledge of context-free grammar and language. Click Here.

The derivation tree is also called the parse tree.

The derivation tree is used to show the given input string is derived from the context-free grammar(CFG).

We discussed the acceptance of string examples in the previous class. Click Here.

We derive in two ways.

1) Left Most Derivation

2) Right Most Derivation

We take an example and understand how we do the left and rightmost derivation.

Example:

Given CFG.

S – aAS | a

A – SbA | SS | ba

Take an input string aabbaa.

The below diagram shows the leftmost derivation of the input string aabbaa.

We start from the start symbol S.

We start elaborating the production from left to right. We call it left most derivation.

First, we take the production S – aAS to derive the input string.

We check for input symbol a and start expanding A. After completing A, we move to symbol S.

We call left most derivation the expansion of nonterminals from left to right.

Now we expand A using A – SbA.

We can show one possible way to derive the input string using the given CFG. The string is accepted.

Now we expand S as S – a.

We had seen two a’s. Then followed by b. now we expand A.

Similarly, we move the expansion from left to right in all productions.

The rightmost derivation is exactly the opposite.

We expand the productions from right to left.

The below diagram shows the rightmost derivation for the input string aabbaa.

First, we take production S – aAS

We start expanding from the right. We expand S, then move to A, and so on.