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 + a …