by Dinesh Thakur

Derivation is used to find whether the string belongs to a given grammar.


Types

• Leftmost derivation.

• Rightmost derivation.

Leftmost Derivation

In leftmost derivation, at each and every step the leftmost non-terminal is expanded by substituting its corresponding production to derive a string.

Example

             Leftmost Derivation

Rightmost Derivation

In rightmost derivation, at each and every step the rightmost non-terminal is expanded by substituting its corresponding production to derive a string.

Example

               Rightmost Derivation