CODEWITHSUNDEEP
context-free-grammarambiguous-grammar
k1k4ss0
k1k4ss0

Reputation: 139

why is this a ambiguous grammar?

I have the following excercise:

Demostrate this grammar is ambiguous:

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

By the theory that I've read a grammar can be ambiguous if:

1) A string W ∈ L(G), generates two differents trees 
2) Makes 2 or more left/right derivations

So, i couldnt determinate a string that confirms 1) , so i've tryed with 2).For what i understand just need 2 reflexive derivations to get my grammar as ambiguous??

for example: 

w=bbaa S->bA->bbAA->bbaA->bbaa 
                ^^--here i made two reflexive/recursive derivation

Is this correct as i described or need more detailled information ?

PD: is there any tip for get strings that generates two threes ??

Upvotes: 0

Views: 238

Answers (1)

Michael Dyck
Michael Dyck

Reputation: 2458

No, this is not a correct demonstration of ambiguity.

Your understanding of point #2 is flawed. A grammar G is ambiguous iff some w in L(G) has more than one leftmost (or rightmost) derivation. You've shown one leftmost derivation for w=bbaa, so if you could show another (i.e., a different leftmost derivation for the same string), that would demonstrate ambiguity. However, there doesn't appear to be one, so you'll have to pick a different string.

Note that this has nothing to do with whether a derivation involves the application of recursive/reflexive productions.

Upvotes: 1

Related Questions