# Production (computer science)

## Method of symbol substitution / From Wikipedia, the free encyclopedia

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 $P$ is the main component in the specification of a formal grammar (specifically a generative grammar). The other components are a finite set $N$ of nonterminal symbols, a finite set (known as an alphabet) $\Sigma$ of terminal symbols that is disjoint from $N$ and a distinguished symbol $S\in N$ that is the *start symbol*.

This article needs additional citations for verification. (November 2012) |

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

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

where $V:=N\cup \Sigma$ is the *vocabulary*, ${}^{*}$ is the Kleene star operator, $V^{*}NV^{*}$ indicates concatenation, $\cup$ denotes set union, and $\setminus$ denotes set minus or set difference. If we do not allow the start symbol to occur in $v$ (the word on the right side), we have to replace $V^{*}$ by $(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:

- $N\to (N\cup \Sigma )^{*}$