*78*

# Derivation

Derivation is a sequence of production rules. It is used to get the input string through these production rules. During parsing, we have to take two decisions. These are as follows:

- We have to decide the non-terminal which is to be replaced.
- We have to decide the production rule by which the non-terminal will be replaced.

We have two options to decide which non-terminal to be placed with production rule.

## 1. Leftmost Derivation:

In the leftmost derivation, the input is scanned and replaced with the production rule from left to right. So in leftmost derivation, we read the input string from left to right.

### Example:

**Production rules:**

**Input**

**The leftmost derivation is:**

## 2. Rightmost Derivation:

In rightmost derivation, the input is scanned and replaced with the production rule from right to left. So in rightmost derivation, we read the input string from right to left.

### Example

**Production rules:**

**Input**

**The rightmost derivation is:**

When we use the leftmost derivation or rightmost derivation, we may get the same string. This type of derivation does not affect on getting of a string.

## Examples of Derivation:

### Example 1:

Derive the string “abb” for leftmost derivation and rightmost derivation using a CFG given by,

**Solution:**

**Leftmost derivation:**

**Rightmost derivation:**

### Example 2:

Derive the string “aabbabba” for leftmost derivation and rightmost derivation using a CFG given by,

**Solution:**

**Leftmost derivation:**

**Rightmost derivation:**

### Example 3:

Derive the string “00101” for leftmost derivation and rightmost derivation using a CFG given by,

**Solution:**

**Leftmost derivation:**

**Rightmost derivation:**