S => SAS | b - A => ba | b - For the string bbabbbbab derive (i) Leftmost derivation (ii) Rightmost derivation (iii) Parse tree

(i) Leftmost derivation

Consider

S => SAS

S => bAS (as S => b)

S => bbaS (as A => ba)

S => bbaSAS (as S => SAS)

S => bbabAS (as S => b)

S => bbabbS (as A => b)

S => bbabbSAS (as S => SAS)

S => bbabbbAS (as S => b)

S => bbabbbbaS ( as A => ba)

S => bbabbbbab (as S => b)

(ii) Rightmost derivation

Consider

S => SAS

S => SAb (as S => b)

S => Sbab (as A=> ba)

S => SASbab (as S => SAS)

S => SAbbab (as S => b)

S => Sbbbab (as A => b)

S => SASbbbab (as S => SAS)

S => SAbbbbab (as S => b)

S => Sbabbbbab (as A => ba)

S => bbabbbbab (as S => b)

(iii) Parse tree