[Overview] [Previous] [Next]

Ambiguity

The following grammar generates strings having an equal number of a's and b's.

G = ({S}, {a, b}, S, S goes to aSb | bSa | SS | empty string)

The string "abab" can be generated from this grammar in two distinct ways, as shown by the following derivation trees:
a derivation tree for abab another derivation tree for abab

Similarly, abab has two distinct leftmost derivations:

S directly derives aSb directly derives abSab directly derives abab
S directly derives SS directly derives aSbS directly derives abS directly derives abaSb directly derives abab

Likewise, abab has two distinct rightmost derivations:

S directly derives aSb directly derives abSab directly derives abab
S directly derives SS directly derives SaSb directly derives Sab directly derives aSbab directly derives abab

Each derivation tree can be turned into a unique rightmost derivation, or into a unique leftmost derivation. Each leftmost or rightmost derivation can be turned into a unique derivation tree. So these representations are largely interchangeable.

Copyright © 1996 by David Matuszek
Last modified Mar 3, 1996