For the string aabbabba find the following :

(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


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

Please log in to add an answer.

Next up

Read More Questions

If you are looking for answer to specific questions, you can search them here. We'll find the best answer for you.


Study Full Subject

If you are looking for good study material, you can checkout our subjects. Hundreds of important topics are covered in them.

Know More