Ambiguity

1. CFG for aⁿbⁿcᵐdᵐ?
   Stuck? Peek at 3.1.2 Writing CFGs for standard languages

   • Wrap: S → aSb | ε (aⁿbⁿ); ratios S → aSbb.
   • Nested: outer wrap → inner wrap. Concatenation: S → XY. Union: S → S₁ | S₂. Star: S → S₁S | ε.
   • Palindromes S → aSa | bSb | a | b | ε. Balanced S → SS | (S) | ε. #a = #b: S → aSbS | bSaS | ε.
   • i ≠ j: S → AC | CB, C → aCb | ε, A → aA | a, B → bB | b.

   Read lesson 3.1.2

2. What corresponds one-to-one with parse trees?
   Stuck? Peek at 3.1.1 Context-free grammars, derivations and parse trees

   • CFG: A → α, single variable on the left. CFL = L(G) for some CFG. Regular ⊂ CFL.
   • Leftmost / rightmost derivations; parse tree with yield = leaves left to right.
   • Trees ↔ leftmost derivations ↔ rightmost derivations (one-to-one per string).

   Read lesson 3.1.1

3. Is the minimal DFA unique?
   Stuck? Peek at 1.3.1 Unreachable, equivalent and distinguishable states

   • Step 0: delete unreachable states (BFS from q₀).
   • p ≡ q ⇔ ∀w: δ̂(p,w) ∈ F ⇔ δ̂(q,w) ∈ F. Distinguishable ⇔ some w separates.
   • ≡₀ = {F, Q−F}; ≡ₖ₊₁ splits by where symbols lead w.r.t. ≡ₖ; stop when stable.
   • Merge classes → minimal DFA, unique up to renaming.

   Read lesson 1.3.1

A calculator reads 2 + 3 * 4. Is it (2 + 3) * 4 = 20 or 2 + (3 * 4) = 14? If the grammar allows both parse trees, the meaning is undefined — a real bug class in compilers. A grammar with two trees for one string is ambiguous. GATE asks you to spot ambiguity, prove it, and know that some languages cannot avoid it.

Grammar E → E + E | E * E | id. How many different parse trees does id + id * id have?

Prediction check

Two: one with + at the root (multiplication done first), one with * at the root (addition first). So this grammar is ambiguous.

Definition

Two different derivations alone prove nothing: one leftmost and one rightmost derivation of the same tree are normal. Compare like with like.

Proving a grammar ambiguous

Exhibit one string and two distinct parse trees (or two leftmost derivations). Classic witnesses:

• E → E+E | E*E | id: id+id*id.
• S → SS | (S) | ε: ()()() (group left or right), and even ε (S ⇒ ε or S ⇒ SS ⇒ S ⇒ ε).
• Dangling else: S → if c then S | if c then S else S | a — the else can attach to either if.
• S → aS | Sa | a: aa (left or right growth).

Removing ambiguity (when possible)

Encode precedence and associativity with layered variables: E → E + T | T, T → T * F | F, F → (E) | id. Now * is always deeper than + and both group to the left; every string has one tree.

Inherent ambiguity

Standard example: L = { aⁱbʲcᵏ : i = j or j = k }. Strings aⁿbⁿcⁿ satisfy both conditions and get one tree from each half of any grammar. Ambiguity is usually a property of a grammar; inherent ambiguity is a property of a language.

Facts to know: there is no general algorithm that decides whether a CFG is ambiguous (proved in Phase 5); every regular language has an unambiguous grammar.

Putting it together

• Ambiguity = two parse trees for one string; prove it with one witness.
• Precedence layers remove ambiguity in expression grammars.
• Some CFLs are inherently ambiguous; no algorithm decides ambiguity in general.

dangling else:   if c then  if c then a  else a
                 └──────── outer ────────────────┘
                            └─ inner ─┘            else → inner?  (tree 1)
                            └──────── inner ───┘   else → outer?  (tree 2)

Grammars can be messy: useless variables, ε-rules, chains like A → B. Next chapter cleans them up and brings every CFG into a standard shape — Chomsky Normal Form — which makes derivation lengths predictable and powers the membership algorithm.

1. MCQ

   A grammar is ambiguous iff some string has two distinct:

   1. derivations
   2. parse trees
   3. rightmost and leftmost derivations
   4. sentential forms
2. MSQ

   Which grammars are ambiguous?

   1. S → SS | a
   2. S → aS | a
   3. S → aSb | ε
   4. S → AB | aB, A → a, B → b
3. MCQ

   Which language is inherently ambiguous?

   1. {aⁿbⁿ}
   2. {aⁱbʲcᵏ : i = j or j = k}
   3. (a+b)*
   4. palindromes
4. NAT

   How many parse trees does S → SS | a give for aaa?

   Write your answer before opening the key.

• ambiguous grammar
• unambiguous grammar
• inherently ambiguous language
• precedence / associativity layering
• dangling else

1. Definition of an ambiguous grammar?
   Reveal answer

   Some string has two or more parse trees (two leftmost derivations).
2. Standard inherently ambiguous language?
   Reveal answer

   { aⁱbʲcᵏ : i = j or j = k }
3. Is S → SS | a ambiguous? Witness?
   Reveal answer

   Yes: aaa.
4. Can an ambiguous grammar generate a regular language?
   Reveal answer

   Yes, e.g. S → aS | Sa | a.