Context-Free Grammars & Derivations

a production rule

Think of a production rule as a single entry in a dictionary of substitutions: 'wherever you see this placeholder, you are allowed to swap in this sequence.' It is the basic move of a grammar, the one operation you repeat to build a string. A grammar is just a finite pile of these rules plus a starting point.

A production rule in a context-free grammar has the form A → α, read 'A may be rewritten as α' or 'A produces α'. The left-hand side A is a single variable (nonterminal). The right-hand side α is any string made of variables and terminals — possibly empty, written ε (epsilon), in which case A may simply vanish. When several rules share the same left side, A → α and A → β, we usually abbreviate them with a vertical bar: A → α | β, which is two rules, not one. To apply a rule, you find an A somewhere in your current string and replace that one occurrence with the rule's right-hand side.

Production rules are where the recursion lives. A rule like E → E + E mentions E on both sides, so you can apply it again and again to build deeper and deeper expressions; a rule like A → a A b lets you generate a's and b's in lockstep. The number and shape of the rules entirely determine the language generated. A subtle point: the SAME set of strings can usually be generated by many different rule sets, so two very different-looking grammars can be equivalent — and deciding whether two arbitrary CFGs are equivalent turns out to be undecidable.

The rule A → 0 A 1 has left side A (one variable) and right side 0 A 1 (terminal, variable, terminal). Applied to the string 'x A y' it yields 'x 0 A 1 y'. Combined with A → ε it generates the language { 0^n 1^n : n ≥ 0 }.

A → α: replace one occurrence of variable A with the right-hand side α.

The bar A → α | β is shorthand for TWO separate rules sharing a left side, not a single rule. And the empty right-hand side ε is allowed: a rule A → ε lets the variable A disappear.

Also called
productionrewrite rule生成規則重寫規則