Ambiguity in Context-Free Grammars: Decision, Justification, and Elimination Strategies for (A \to AA \mid (A) \mid a)

In formal language theory, a context-free grammar (CFG) is called ambiguous if there exists at least one string in its language that has more than one distinct parse tree (equivalently, more than one distinct leftmost/rightmost derivation) under the same grammar. This concept is central because ambiguity makes parsing nondeterministic: the grammar does not prescribe a unique structural interpretation for a sentence.

Ambiguous CFG and Parse tree are the key notions.

To address your specific grammar [ A \to AA \mid (A) \mid a, ] we will (i) characterize what strings it generates, (ii) construct explicit distinct parse trees for some string if ambiguity exists, or (iii) argue that every string has a unique parse tree if the grammar is unambiguous. We will also cover standard techniques to eliminate ambiguity when possible.

Mermaid sketch of ambiguity criterion:

Note: “remove ambiguity” is subtle: sometimes ambiguity can be eliminated by transforming the grammar; sometimes it is inherent to the generated language (no CFG for the language can avoid ambiguity), or the current CFG can be replaced by a different (unambiguous) one.

3

1) What strings does (A \to AA \mid (A) \mid a) generate?

Intuitively, the grammar builds:

• atomic symbols: (a)
• parenthesized expressions: ((A))
• concatenations of two (A)’s: (AA)

The production (AA) gives concatenation, while ((A)) gives grouping, and (a) provides the base case.

A crucial observation: because concatenation is produced by recursively splitting into two parts in any way, the structure for a given string may admit multiple hierarchical decompositions—this is a classic source of ambiguity in CFGs.

Key terms: Context-free grammar; Derivation; Leftmost derivation; Rightmost derivation.

2

2) Direct ambiguity proof: show two different parse trees for the same string

Consider the string (aa).

Parse Tree option 1 (use (AA) split as (a\cdot a)):

• Derive (A \Rightarrow AA)
• Left (A \Rightarrow a)
• Right (A \Rightarrow a)

So: [ A \Rightarrow AA \Rightarrow aA \Rightarrow aa. ]

Parse Tree option 2 (via a different derivation structure): We need to check carefully: to get a different parse tree for the same string (aa), we must use productions that generate terminals. The only terminals are produced by (A \to a). Parentheses introduce literal “(” and “)”, which cannot appear in the target string (aa). Therefore, any derivation generating (aa) must use only the base production (A\to a) and the concatenation production (A\to AA).

Now observe: to produce exactly two terminals (a a), the root must be (AA) (since there is no production (A\to aa) directly). Then each child must produce exactly one terminal (a), hence both children must be derived as (A\Rightarrow a).

That means, for the string (aa), there is effectively one parse structure: the root is (AA) with leaves (a) and (a). So (aa) alone does not certify ambiguity.

So we move to a slightly longer string where multiple parenthesizations of concatenation become possible.

3) Ambiguity certified by the string (aaa)

Now look at the string (aaa).

There are (at least) two distinct ways to structure a binary concatenation of three (a)’s:

• ((a a) a)
• (a (a a))

Both correspond to different parse trees because the grammar builds concatenation via a binary rule (A\to AA), and different binary-groupings yield different trees while producing the same yield.

Derivation / parse structure 1: ((aa)a) [ A \Rightarrow AA ] Left child generates (aa), right child generates (a): [ A \Rightarrow AA \Rightarrow (AA)A \Rightarrow (aA)A \Rightarrow (aa)A \Rightarrow (aa)a = aaa. ]

Derivation / parse structure 2: (a(aa)) Again: [ A \Rightarrow AA ] Left child generates (a), right child generates (aa): [ A \Rightarrow AA \Rightarrow A(AA) \Rightarrow a(AA) \Rightarrow a(aA) \Rightarrow a(aa)=aaa. ]

These two derivations correspond to different parse trees: in one, the left subtree expands to an (AA) before combining with the final (a); in the other, the right subtree does.

Therefore, the grammar is ambiguous.

Mermaid visualization of two binary parse shapes (same yield (aaa)):

This directly matches the definition: same string (aaa), two distinct parse trees, hence ambiguity.

Key terms: Ambiguity witness; Parse ambiguity; Binary parse structure.

2

4) Can ambiguity be removed? Techniques and justification

There is no single universal “ambiguity removal” method that works for all CFGs. However, there are well-known approaches:

1. Grammar refactoring / restructuring
   Transform productions to enforce a unique parse structure (e.g., encode precedence/associativity explicitly, eliminate ambiguous recursion patterns).

2. Enforcing associativity using separate nonterminals
   For example, if the ambiguity comes from concatenation associativity, introduce nonterminals that represent “left-associative concatenation” vs “right-associative concatenation,” or use EBNF-style repetition in a way that corresponds to a unique parse.

3. Use of deterministic parsing classes (LL/LR) as a design constraint
   If you can create an equivalent unambiguous grammar that fits LL(1), LR(1), etc., then ambiguity disappears for those grammars because deterministic parsing implies unique parse trees for valid inputs.

We can illustrate technique (2) by showing what an unambiguous variant would look like. Since the ambiguity stems from (AA), one can enforce a specific associativity for concatenation.

For instance, a left-associative concatenation form could be: [ A \to L,\quad L \to L,F \mid F,\quad F \to (A)\mid a ] This makes concatenation grouping deterministic: the rule (L\to L,F) forces a left-nested structure.

Conceptually, this turns the set of binary trees that produce (aaa) from two possibilities into a single allowed one (only the left-nested tree).

Important: This does not “remove ambiguity” magically; it replaces the original grammar with a different one that generates the same language but is unambiguous (here, by fixing associativity of concatenation).

Key terms: Refactoring; Associativity; Unambiguous grammar.

2