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 template message)

A production or production rule in computer science is a rewrite rule specifying a symbol substitution that can be recursively performed to generate new symbol sequences. A finite set of productions ${\displaystyle P}$ is the main component in the specification of a formal grammar (specifically a generative grammar). The other components are a finite set ${\displaystyle N}$ of nonterminal symbols, a finite set (known as an alphabet) ${\displaystyle \Sigma }$ of terminal symbols that is disjoint from ${\displaystyle N}$ and a distinguished symbol ${\displaystyle S\in N}$ that is the start symbol.

In an unrestricted grammar, a production is of the form ${\displaystyle u\to v}$, where ${\displaystyle u}$ and ${\displaystyle v}$ are arbitrary strings of terminals and nonterminals, and ${\displaystyle u}$ may not be the empty string. If ${\displaystyle v}$ is the empty string, this is denoted by the symbol ${\displaystyle \epsilon }$, or ${\displaystyle \lambda }$ (rather than leave the right-hand side blank). So productions are members of the cartesian product

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

where ${\displaystyle V:=N\cup \Sigma }$ is the vocabulary, ${\displaystyle {}^{*}}$ is the Kleene star operator, ${\displaystyle V^{*}NV^{*}}$ indicates concatenation, ${\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\})^{*}}$ on the right side of the cartesian product symbol.^[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 (N\cup \Sigma )^{*}}$