Production (computer science)

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Production" computer science – news · newspapers · books · scholar · JSTOR (November 2012) (Learn how and when to remove this message)

In computer science, a production or production rule is a rewrite rule that replaces some symbols with other symbols. A finite set of productions ${\displaystyle P}$ is the main component in the specification of a formal grammar (specifically a generative grammar).

In such grammars, a set of productions is a special case of relation on the set of strings ${\displaystyle V^{*}}$ (where ${\displaystyle {}^{*}}$ is the Kleene star operator) over a finite set of symbols ${\displaystyle V}$ called a vocabulary that defines which non-empty strings can be substituted with others. The set of productions is thus a special kind subset

${\displaystyle P\subset V^{*}\times V^{*}}$

and productions are then written in the form ${\displaystyle u\to v}$ to mean that ${\displaystyle (u,v)\in P}$ (not to be confused with ${\displaystyle \to }$ being used as function notation, since there may be multiple rules for the same ${\displaystyle u}$). Given two subsets ${\displaystyle A,B\subset V^{*}}$, productions can be restricted to satisfy ${\displaystyle P\subset A\times B}$, in which case productions are said "to be of the form ${\displaystyle A\to B}$. Different choices and constructions of ${\displaystyle A,B}$ lead to different types of grammars. In general, any production of the form

${\displaystyle u\to \epsilon ,}$

where ${\displaystyle \epsilon }$ is the empty string (sometimes also denoted ${\displaystyle \lambda }$), is called an erasing rule, while productions that would produce strings out of nowhere, namely of the form

${\displaystyle \epsilon \to v,}$

are never allowed.

In order to allow the production rules to create meaningful sentences, the vocabulary is partitioned into (disjoint) sets ${\displaystyle \Sigma }$ and ${\displaystyle N}$ providing two different roles:

• ${\displaystyle \Sigma }$ denotes the terminal symbols known as an alphabet containing the symbols allowed in a sentence;
• ${\displaystyle N}$ denotes nonterminal symbols, containing a distinguished start symbol ${\displaystyle S\in N}$, that are needed together with the production rules to define how to build the sentences.

In the most general case of an unrestricted grammar, a production ${\displaystyle u\to v}$, is allowed to map arbitrary strings ${\displaystyle u}$ and ${\displaystyle v}$ in ${\displaystyle V}$ (terminals and nonterminals), as long as ${\displaystyle u}$ is not empty. So unrestricted grammars have productions of the form

${\displaystyle V^{*}\setminus \{\epsilon \}\to V^{*}}$

or if we want to disallow changing finished sentences

${\displaystyle V^{*}NV^{*}=(V^{*}\setminus \Sigma ^{*})\to V^{*}}$,

where ${\displaystyle V^{*}NV^{*}}$ indicates concatenation and forces a non-terminal symbol to always be present in of the left-hand side of the productions, ${\displaystyle \cup }$ denotes set union, and ${\displaystyle \setminus }$ denotes set minus or set difference. If we do not allow the start symbol to occur in ${\displaystyle v}$ (the word on the right side), we have to replace ${\displaystyle V^{*}}$ by ${\displaystyle (V\setminus \{S\})^{*}}$ in the right-hand side.^[1]

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:

${\displaystyle N\to V^{*}}$