Consider the grammer S → SbS | a.
Consider the following statements:
The string abababa has
(A) two parse trees
(B) two left most derivations
(C) two right most derivations
Which of the following is correct?
Solution
The given grammar is:
S → SbS | a
The string abababa can be derived using the:
(A) two parse trees

(B) two left most derivative
First derivative
S → SbS
S → SbSbS
S → SbSbSbS
S → abSbSbS
S → ababSbS
S → abababS
S → abababa
Second derivative
S → SbS
S → abS
S → abSbS
S → ababS
S → ababSbS
S → abababS
S → abababa
(C) two right most derivative
First derivative
S → SbS
S → SbSbS
S → SbSbSbS
S → SbSbSba
S → SbSbaba
S → Sbababa
S → abababa
Second derivative
S → SbS
S → Sba
S → SbSba
S → Sbaba
S → SbSbaba
S → Sbababa
S → abababa
Hence, the correct answer is options 1.