Mumbai University > Information Technology > Sem 4 > Automata Theory

Marks: 5M

Let G be the Grammar. Find the leftmost derivation,rightmost derivation and parse tree for the expression ab+ab

G : S => S+S|S*S

S => a|b

Leftmost derivation:

S => S + S

S => SS + S (as S =>SS)

S => a*S + S (as S =>a)

S => a*b + S (as S =>b)

S => ab + SS (as S => S*S)

S => ab + aS (as S => a)

S => ab + ab (as S => b)

Rightmost derivation:

S => S + S

S => S + SS (as S =>SS)

S => S + S*b (as S =>b)

S => S + a*b (as S =>a)

S => SS + ab (as S => S*S)

S => Sb + ab (as S => b)

S => ab + ab (as S => a)

Parse Tree: