Question: For the string aabbabba find the following :
0

(i) Leftmost derivation

(ii) Rightmost derivation

(iii) Parse tree

Given the following Grammar:

S => aB | bA

S => a | aS | bAA

S => b | bS | aBB

Mumbai university > Comp > SEM 4 > TCS

Marks: 10M

Year: May 2014

ADD COMMENTlink
modified 3.3 years ago  • written 3.3 years ago by gravatar for Pooja Joshi Pooja Joshi740
0

The question is incomplete there must be two more productions to be added

*A => aS | a

*B => bS | b

(i) Leftmost derivation

S => aS

S => aaBB (as S => aBB)

S => aabB (as B => b)

S => aabbS (as B => bS)

S => aabbaB (as S => aB)

S => aabbabS (as B => bS)

S => aabbabbS (as S => bS)

S => aabbabba (as S => a)

(ii) Rightmost derivation

S => aS

S => aaBB (as S => aBB)

S => aaBB (as B => b)

S => aaBbS (as B => bS)

S => aaBbaB (as S => aB)

S => aaBbabS (as B => bS)

S => aaBbabbS (as S =>bS)

S => aaBbabba (as S =>a)

S => aabbabba (as B =>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.