G: S =>0S|1A|2B|ε

A =>1A|2B| ε

B =>2B| ε

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: