Understanding Ambiguity in Context-Free Grammars

Ambiguity in Context-Free Grammars

Definition of CFG Ambiguity

A Context-Free Grammar (CFG) is called ambiguous if, for at least one word in the language it generates, there are two or more possible derivations of the word that correspond to different syntax trees.

Example 1: Simple Ambiguity

Consider the language generated by the following CFG:

PROD 1: S → AB
PROD 2: A → a
PROD 3: B → b

There are two different sequences of production applications that generate the word ab:

• Sequence 1: PROD 1, PROD 2, PROD 3
• Sequence 2: PROD 1, PROD 3, PROD 2

These sequences lead to the following derivations:

S → AB → aB → ab
S → AB → Ab → ab

When the corresponding syntax trees are drawn, we observe that these two derivations are essentially the same, as shown below:

Example 2: The PALINDROME Language

Consider the language PALINDROME, defined by the CFG below:

S → aSa | bSb | a | b | λ

At every stage in the generation of a word by this grammar, the working string contains only the single nonterminal S, positioned centrally. The word grows like a tree from the center outwards.

For instance, a derivation might look like this:

... baSab → babSbab → babbSbbab → babbaSabbab ...

When we finally replace S by a center letter (or by the empty string λ if the word has an even length), we have completed the production of a palindrome.

The word aabaa has only one possible generation sequence:

S → aSa
  → aaSaa
  → aabaa

The unique syntax tree for aabaa is:

Example 3: Non-Empty Strings of 'a's

The language of all non-empty strings of 'a's can be defined by a CFG as follows:

S → aS | Sa | a

In this case, the word a³ (aaa) can be generated by four different syntax trees, as shown in the following images:

This CFG is therefore ambiguous.

However, the same language can also be defined by the following unambiguous CFG:

S → aS | a