The following grammar G is ambiguous find an equivalent gram

The following grammar G is ambiguous, find an equivalent grammar that is not ambiguous.

S AB, A AA | a, B Tb, T aT | a

Please explain or give valid reason. Thanks for your help!

Solution

A)

an ambiguous grammar is a context-free grammar for which there exists a string that can have more than one leftmost derivation, while an unambiguous grammar is a context-free grammar for which every valid string has a unique leftmost derivation.

Many languages admit both ambiguous and unambiguous grammars, while some languages admit only ambiguous grammars.

While derivations are not unique, even if the grammar is unambiguous, it turns out
that, in an unambiguous grammar, leftmost derivation will be unique, and rightmost
derivations will be unique.

We shall consider leftmost derivations only, and state the result for rightmost derivations.

S --> AB, A --> AA | a, B --> Tb, T --> aT | a

LeftMost Derivation:                                              RightMost Derivation:

S --> AB           S --> AB                                         S --> AB                           S --> AB

--> aB                  --> AAB                                          --> ATb                            --> ATb

--> aTb    (or)           --> aAB                                        --> AaTb             (or)        --> Aab

--> aaTb                   --> aaTb                                        --> Aaab                        --> AAab

--> aaab                 --> aaab                                            --> aaab                        --> Aaab

                                                                                                                            --> aaab

for the string w = aaab we can derive morethan 1 left or right most derivations hence it is ambiguous.

S --> AB

A --> aA | a

B --> b

The above grammar is an equivalent unambiguous grammar for the given ambiguous grammar G.