Let G be the grammar. Find the leftmost derivation, rightmost derivation and parse tree for the string 001222.
G: S =>0S|1A|2B|ε
A =>1A|2B| ε
B =>2B| ε
If we solve the sum using the given grammar, we can produce the string using leftmost derivation alone, but not the rightmost derivation.
A language with a leftmost derivation must also have a rightmost derivation, so we modify the grammar to solve the sum in both leftmost as well as rightmost derivation.
Modified grammar is :
G: S =>0S|1A|2B|ε
A =>1A|2B| ε
B =>2BB| ε
Production of B change from B =>2B to B =>2BB
Leftmost derivation:
S =>0S
S => 00S (as S =>0S)
S =>001A (as S =>1A)
S => 0012B (as A =>2B)
S => 00122BB (as B =>2BB)
S => 00122B2BB (as B =>2BB)
S => 001222BB (as B =>ε )
S => 001222B (as B =>ε )
S => 001222 (as B =>ε )
Rightmost derivation:
S =>0S
S => 00S (as S =>0S)
S =>001A (as S =>1A)
S => 0012B (as A =>2B)
S => 00122BB (as B =>2BB)
S => 00122B2BB (as B =>2BB)
S => 00122B2B (as B =>ε )
S => 00122B2 (as B =>ε )
S => 001222 (as B =>ε )
Parse tree: