Introduction to Automata

Rightmost Derivation in Automata

Getting a string by expanding the rightmost non-terminal at each step is called rightmost derivation in Automata.

• The representation of rightmost derivation in a tree is called a rightmost derivation tree.
• In the rightmost derivation tree, we read the given input string (W) from left to right.

Example of Rightmost Derivation

Consider the following production rules of a Grammar (G)

S → xB / yA

S → xS / yAA / x

B → yS / xBB / y

Consider a string W = xxxyyxyyyx

Using grammar production rules, let us derive the given string (W= xxxyyxyyyx). And we will also draw the derivation tree of each step as given below.

Rightmost Derivation and Tree

Let us see derivation through production rules and their tree as given below

Step 01: S   → xB                     (Using S → xB)

Step 02: W=  xxBB                    (Using B → xBB)

Step 03: W=  xxBxBB                 (Using B → xBB)

Step 04: W=  xxBxByS               (Using B → yS)

Step 05: W=  xxBxByyA             (Using S → yA)

Step 06: W= xxBxByyx              (Using A → x)

Step 07: W= xxBxyyyx              (Using B → y)

Step 08: W=  xxxBBxyyyx          (Using B → xBB)

Step 09: W=  xxxByxyyyx          (Using B → y)

Step 10: W= xxxyyxyyyx           (Using B → y)

Hence, the given String (W=xxxyyxyyyx) is derived through the Rightmost derivation. So, the given string belongs to the Given Grammar (G).