0
Consider the following grammar

S => SAS | b

A => ba | b

For the string bbabbbbab derive (i) Leftmost derivation (ii) Rightmost derivation (iii) Parse tree

Mumbai university > Comp > SEM 4 > TCS

Marks: 10M

Year: Dec 2014

0
0

(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

enter image description here

0
Please log in to add an answer.

Continue reading

Find answer to specific questions by searching them here. It's the best way to discover useful content.

Find more