A production in computer science is a rewrite rule specifying a symbol substitution that can be recursively performed to generate new symbol sequences. A set of productions specifies a formal grammar, specifically a generative grammar. A special "start symbol" is used to begin the sequence construction, which then proceeds by the substitution of "terminal symbols" (which cannot themselves be the target of substitution) and "non-terminal symbols" (which are available for further substitution). The complete set of terminal-only strings represents the grammar.
Grammar generation
To generate a string in the language, one begins with a string consisting of only a single start symbol, and then successively applies the rules (any number of times, in any order) to rewrite this string. The language consists of all the strings that can be generated in this manner. Any particular sequence of legal choices taken during this rewriting process yields one particular string in the language. If there are multiple different ways of generating a single string, then the grammar is said to be ambiguous. For example, assume the alphabet consists of <math>a</math> and <math>b</math>, the start symbol is <math>S</math> and we have the following rules:
- 1. <math>S \rightarrow aSb</math>
- 2. <math>S \rightarrow ba</math>
then we start with <math>S</math>, and can choose a rule to apply to it. If we choose rule 1, we replace <math>S</math> with <math>aSb</math> and obtain the string <math>aSb</math>. If we choose rule 1 again, we replace <math>S</math> with <math>aSb</math> and obtain the string <math>aaSbb</math>. This process is repeated until we only have symbols from the alphabet (i.e., <math>a</math> and <math>b</math>). If we now choose rule 2, we replace <math>S</math> with <math>ba</math> and obtain the string <math>aababb</math>, and are done. We can write this series of choices more briefly, using symbols: <math>S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow aababb</math>. The language of the grammar is the set of all the strings that can be generated using this process: <math>\left \{ba, abab, aababb, aaababbb, ...\right \}</math>.
