CFG Derivations, Ambiguity Proofs & Chomsky Normal Form

A Context-Free Grammar (CFG) is a 4-tuple G = (V, T, P, S), where production rules have the form A \to \alpha, with A \in V (a single non-terminal variable) and \alpha \in (V \cup T)^*.

Ambiguity in Grammars:

A grammar G is ambiguous if there exists at least one string w \in L(G) that has two or more distinct leftmost derivations (or equivalently, two or more distinct parse trees).

Inherent Ambiguity:

A context-free language L is inherently ambiguous if EVERY grammar that generates L is ambiguous. Classic inherently ambiguous language:

$L = { a^n b^n c^m d^m \mid n, m ≥ 1 } \cup { a^n b^m c^m d^n \mid n, m ≥ 1 }$

For strings where n = m (a^n b^n c^n d^n), every grammar is forced to generate duplicate parse trees.

Chomsky Normal Form (CNF):

A grammar is in CNF if all production rules are strictly of the form: A \to BC or A \to a (where A, B, C \in V and a \in T).

CNF Derivation Length Theorem: If a string w \in L(G) has length n ≥ 1, any derivation of w in a CNF grammar requires EXACTLY 2n - 1 steps (specifically: n - 1 rule applications of A \to BC, followed by n rule applications of A \to a).