What is ambiguous grammar ? Find if the following grammar is ambigous or not ?

2.0kviews

written 5.9 years ago by

teamques10 ★ 68k

• modified 5.6 years ago

S -> S + S

S -> S * S

S -> a

S -> b

Mumbai University > Information Technology > Sem 4 > Automata Theory

Marks : 10M

automata theory

ADD COMMENT EDIT

1 Answer

24views

written 5.6 years ago by

teamques10 ★ 68k

modified 5.6 years ago by

ankitpandey • 100

S $\rightarrow$ S + S

S * S

Consider derivation of A + b + a * b

LMD

enter image description here

S $\rightarrow$ S + S

S + S + S

A + s + s

A + b + s

A+ b + s * s

A + b + a * s

A + b + a * b

RMD

enter image description here

S $\rightarrow$ S + S

S * b

S + s * b

S + a * b

S + s + a * b

S + b + a * b

A + b + a * b

As above both trees are different. The given grammar is ambiguous.

ADD COMMENT EDIT

Please log in to add an answer.