## 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:**