Theory of Automata

Leftmost Derivation in Automata

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

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

Example of Leftmost Derivation

Consider the following production rules for the 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

Leftmost Derivation and Tree

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

Step 01: S   → xB                    (W=xB)

Leftmost Derivation Step 01

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

Leftmost Derivation Step 02

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

Leftmost Derivation Step 03

Step 04: W= xxxyBB                (Using B → y)

Leftmost Derivation Step 04

Step 05: W= xxxyyB                (Using B → y)

Leftmost Derivation Step 05

Step 06: W= xxxyyxBB            (Using B → xBB)

Leftmost Derivation Step 06

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

Leftmost Derivation Step 07

Step 08: W= xxxyyxyyS          (Using B → yS)

Leftmost Derivation Step 08

Step 09: W= xxxyyxyyyA        (Using S → yA)

Leftmost Derivation Step 09

Step 10: W= xxxyyxyyyx        (Using A → x)

Leftmost Derivation Step 10

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

Help Other’s By Sharing…

Contact Us

Burewala, Vehari, Punjab, Pakistan


Pin It on Pinterest