Domanda

ive been trying to prove a grammar ambiguous, from my understanding its not, but according to the question; it should be ambiguous. The grammar is

S -> AB | aaB
A -> a | Aa
B -> b

the string ive been using is aaab. From what it seems, i dont see any way the Left and Right trees can be different. To begin with the string is either AB or aaB form, if its aaB form, game over, if its AB form, you can either end with a, or continue another branch in Aa.

È stato utile?

Soluzione

From what I can see, there is exactly one string which has more than one parse tree (or equivalently, more than one left-most derivation): aab

S -> AB -> AaB -> aaB -> aab

or

S -> aaB -> aab

This one string makes the grammar ambiguous.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top