Context-Free Grammars & Derivations

a derivation step

A derivation step is the single atomic move of a grammar: one rewrite, one rule, one variable replaced. If a full derivation is the whole journey from start symbol to finished string, a derivation step is one footstep along the way. Everything a grammar does is just many of these little moves chained together.

Formally, write u => v (one step) when v is obtained from u by taking a single occurrence of a variable A inside u and replacing it with the right-hand side of one production rule A → α. So if u = xAy (with x and y any strings of symbols) and the grammar has the rule A → α, then xAy => xαy in one step. The double-arrow with a star, =>*, is the reflexive-transitive closure: u =>* w means u reaches w in zero or more such steps (zero steps means u equals w). A derivation is then just a chain u0 => u1 => ... => un of individual steps.

The one-step relation is the formal heart of what 'generate' means, and it is what lets us reason about grammars by induction: many proofs about CFGs (for example that a grammar generates a certain language) go by induction on the NUMBER of derivation steps. Note that a single step always rewrites EXACTLY ONE occurrence of one variable — you cannot rewrite two variables in one step, and which occurrence you pick is a free choice unless you fix a discipline like leftmost or rightmost.

With rule A → 0 A 1, the string '0 A 1' becomes '0 0 A 1 1' in one step: 0A1 => 00A11. We replaced the single A by its right-hand side 0 A 1, leaving the surrounding symbols untouched.

u => v: replace exactly one occurrence of one variable using one rule; =>* chains zero or more such steps.

One step rewrites exactly one occurrence of one variable — never two at once. The starred =>* allows zero steps, so w =>* w always holds.

Also called
one-step derivationdirect derivation單步推導直接推導