Theory of Automata

Rightmost Derivation in Automata



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

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

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



Let us derive the given string (W= xxxyyxyyyx) by using given production rules of grammar. And 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)

Rightmost Derivation Step 01

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

Rightmost Derivation Step 02

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

Rightmost Derivation Step 03

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

Rightmost Derivation Step 04



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

Rightmost Derivation Step 05

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

Rightmost Derivation Step 06

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

Rightmost Derivation Step 07



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

Rightmost Derivation Step 08

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

Rightmost Derivation Step 09

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

Rightmost Derivation Step 10

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

Help Other’s By Sharing…

Contact Us

Burewala, Vehari, Punjab, Pakistan

cstaleem1@gmail.com

Website: CStaleem.com

Pin It on Pinterest