How can I prove that this grammar is ambiguous?

Question

S -> bA|aB
A -> a|aS|bAA
B -> b|bS|aBB

Any simple method besides trying to find a string that will generate two parsing trees?

Can someone please give me a line that can prove it.

+5

crowso Feb 02 '11 at 18:39

2 answers

There is a line: bbaaba

S -> bA -> bbAA -> bbaA -> bbaaS -> bbaabA -> bbaaba
S -> bA -> bbAA -> bbaSA -> bbaaBA -> bbaabA -> bbaaba

+16

Shweta Mar 24 '13 at 10:08

Jim lewis · Accepted Answer · 2011-02-02T18:56:52+0000

There is no simple method of proving the ambiguity of context-free grammar - in fact, the question is insoluble , by reducing it to a problem with correspondence .