Question: Consider the following grammar
0

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

ADD COMMENTlink
modified 3.3 years ago  • written 3.3 years ago by gravatar for Pooja Joshi Pooja Joshi740
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

ADD COMMENTlink
written 3.3 years ago by gravatar for Pooja Joshi Pooja Joshi740
Please log in to add an answer.