Context-Free Grammars & Derivations

the start symbol

Every story has a first sentence, and every derivation has a first symbol. The start symbol is the one distinguished placeholder you ALWAYS begin from when generating a string. Without it, you would not know which rules to apply first; with it, the whole grammar springs from a single seed.

Formally, in a context-free grammar (V, Σ, R, S), the start symbol S is a chosen element of the set of variables V. To generate any string of the language you begin with just S and apply production rules until only terminals remain. By the usual convention the start symbol is named S, and when a grammar is written as a list of rules it is the variable on the left of the very first rule. The language of the grammar is defined as exactly the set of terminal strings derivable FROM S — derivations that begin from any other variable do not count toward the language.

Choosing the start symbol matters because it fixes what 'a complete program' or 'a complete expression' means: it should be the nonterminal whose category is the whole thing you intend to generate (for a programming language, something like Program). A useful trick in proofs and constructions (for example when putting a grammar into Chomsky normal form) is to introduce a brand-new start symbol S0 with a rule S0 → S, so that the start symbol never appears on any right-hand side — this avoids awkward special cases.

In S → a S a | b S b | ε, the start symbol is S. Every derivation begins S => ... ; for instance S => aSa => abSba => abba, so 'abba' is in the language. A derivation starting from anything but S would not define the language.

The start symbol is the single seed every derivation grows from; the language is what is derivable from it.

The start symbol is always a variable (nonterminal), never a terminal. The language is defined relative to it: strings derivable from other variables are not part of the grammar's language.

Also called
start variablesentence symbol起始變數開始符號