Leftmost and Rightmost Derivation
In Theory of Computation (TOC), when generating strings from a Context-Free Grammar (CFG), we can apply production rules in different orders. Two primary approaches to applying these rules are:
-
Leftmost Derivation
-
Rightmost Derivation
Both methods provide the same string as output, but follow different strategies for replacing non-terminal symbols. Understanding these derivations is crucial for syntax analysis, parse tree construction, and grammar ambiguity detection.
Leftmost and Rightmost Derivation Example
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 leftmost and rightmost derivation. We will also draw the derivation tree of each step.
1. Leftmost Derivation
Getting a string by expanding the leftmost nonterminal at each step is called a leftmost derivation in Automata.
- The representation of leftmost derivation in a tree is called a leftmost derivation tree.
- We read the given input string (W) from left to right in the leftmost derivation tree.
Leftmost Derivation and Tree
Let us see derivation through production rules and their tree as given below.
Step 01: S → xB (W=xB)
Step 02: W= xxBB (Using B → xBB)
Step 03: W= xxxBBB (Using B → xBB)
Step 04: W= xxxyBB (Using B → y)
Step 05: W= xxxyyB (Using B → y)
Step 06: W= xxxyyxBB (Using B → xBB)
Step 07: W= xxxyyxyB (Using B → y)
Step 08: W= xxxyyxyyS (Using B → yS)
Step 09: W= xxxyyxyyyA (Using S → yA)
Step 10: W= xxxyyxyyyx (Using A → x)
Hence the given string (W= xxxyyxyyyx) is derived through leftmost derivation. So, the given string belongs to the Given Grammar (G).
2. 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.
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).