Menu
S -> bA|aB
A -> a|aS|bAA
B -> b|bS|aBB
Any easy method other than trying to find a string that would generate two parse trees ?
Can someone please give me a string that can prove this.
957
More Detail. A Grammar that makes more than one Leftmost Derivation (or Rightmost Derivation) for the similar sentence is called Ambiguous Grammar. Example − Verify whether the following Grammar is Ambiguous or Not. E → E+E|E ∗ E|id.
A grammar is ambiguous if there exists a sequence of token that can be derived by two different leftmost derivations. An obvious question is whether there is a better, unambiguous, grammar for simple expressions.
In computer science, an ambiguous grammar is a context-free grammar for which there exists a string that can have more than one leftmost derivation or parse tree, while an unambiguous grammar is a context-free grammar for which every valid string has a unique leftmost derivation or parse tree.
Detailed Solution The correct answer is option 4. A is ambiguous because λ can be generated using leftmost derivation having two different parse trees with an empty string. B is ambiguous grammar with string abab. C is an ambiguous grammar with string abbbb.
There is a string though: bbaaba
S -> bA -> bbAA -> bbaA -> bbaaS -> bbaabA -> bbaaba
S -> bA -> bbAA -> bbaSA -> bbaaBA -> bbaabA -> bbaaba
There is no easy method for proving a context-free grammar ambiguous -- in fact, the question is undecidable, by reduction to the Post correspondence problem.
31
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
