Production (computer science)


In computer science, a production or production rule is a rewrite rule that replaces some symbols with other symbols. A finite set of productions is the main component in the specification of a formal grammar.
In such grammars, a set of productions is a special case of relation on the set of strings over a finite set of symbols called a vocabulary that defines which non-empty strings can be substituted with others.
The set of productions is thus a special kind subset
and productions are then written in the form to mean that .
Given two subsets, productions can be restricted to satisfy, in which case productions are said "to be of the form.
Different choices and constructions of lead to different types of grammars.
In general, any production of the form
where is the empty string, is called an erasing rule, while productions that would produce strings out of nowhere, namely of the form
are never allowed.
In order to allow the production rules to create meaningful sentences, the vocabulary is partitioned into sets and providing two different roles:
In the most general case of an unrestricted grammar, a production, is allowed to map arbitrary strings and in, as long as is not empty. So unrestricted grammars have productions of the form
or if we want to disallow changing finished sentences
where indicates concatenation and forces a non-terminal symbol to always be present in of the left-hand side of the productions, denotes set union, and denotes set minus or set difference. If we do not allow the start symbol to occur in, we have to replace by in the right-hand side.
The other types of formal grammar in the Chomsky hierarchy impose additional restrictions on what constitutes a production. Notably in a context-free grammar, the left-hand side of a production must be a single nonterminal symbol. So productions are of the form:

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 to rewrite this string. This stops when a string containing only terminals is obtained. 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 this single string, then the grammar is said to be ambiguous.
For example, assume the alphabet consists of and, with the start symbol, and we have the following rules:
then we start with, and can choose a rule to apply to it. If we choose rule 1, we replace with and obtain the string. If we choose rule 1 again, we replace with and obtain the string. This process is repeated until we only have symbols from the alphabet. If we now choose rule 2, we replace with and obtain the string, and are done. We can write this series of choices more briefly, using symbols:. The language of the grammar is the set of all the strings that can be generated using this process:.