Skip to main content

Ambiguity; language of S→SS|a

Short answer

Ambiguity: a string has two or more parse trees. Inherent ambiguity: a language where every CFG is ambiguous. For S → SS | a, L(G) = a⁺ (non-empty strings of a's). The grammar is ambiguous (e.g., aaa has two trees), but the language is not inherently ambiguous (unambiguous grammar S → aS | a exists).

Define ambiguity and inherent ambiguity in a parse tree. For a CFG defined by G = (V, Σ, R, S), V = {S}, Σ = {a}, R = {S → SS; S → a}, obtain the language L(G).

Ambiguity

A CFG is ambiguous if some string in its language has two or more different parse trees (equivalently, two different leftmost derivations, or two different rightmost derivations).

Example: E → E + E | E * E | id. The string id + id * id has two parse trees.

Inherent ambiguity

A context free language is inherently ambiguous if every CFG that generates it is ambiguous; no unambiguous grammar exists for it. Ambiguity of a grammar can often be removed by rewriting it, but not for inherently ambiguous languages.

Example: L = { aⁱbʲcᵏ : i = j or j = k } is inherently ambiguous. Strings with i = j = k can be generated in both ways in any grammar.

Language of G: V = {S}, Σ = {a}, S → SS | a

Claim: L(G) = { aⁿ : n ≥ 1 } = a⁺.

  • (⊆) Every derived terminal string contains only a's, and S ⇒* ε is impossible since there is no ε-production, so each string has at least one a.
  • (⊇) By induction on n. For n = 1: S ⇒ a. If aᵏ ∈ L(G) for all k < n, then for n ≥ 2, S ⇒ SS ⇒* a^(n−1)·a = aⁿ.

So L(G) = a⁺ (any non-empty string of a's).

G is ambiguous

The string aaa has two different parse trees:

  (aa)a grouping        a(aa) grouping
        S                    S
       / \                  / \
      S   S                S   S
     / \  |                |  / \
    S   S a                a S   S
    |   |                    |   |
    a   a                    a   a

Both trees have yield aaa, so G is ambiguous.

However, L(G) = a⁺ is not inherently ambiguous, because the unambiguous grammar S → aS | a generates the same language.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Theory of Computation chapter 3 questions →