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 is the main component in the specification of a formal grammar (specifically a generative grammar). The other components are a finite set
of nonterminal symbols, a finite set (known as an alphabet)
of terminal symbols that is disjoint from
and a distinguished symbol
that is the start symbol.
This article needs additional citations for verification. (November 2012) |
In an unrestricted grammar, a production is of the form , where
and
are arbitrary strings of terminals and nonterminals, and
may not be the empty string. If
is the empty string, this is denoted by the symbol
, or
(rather than leaving the right-hand side blank). So productions are members of the cartesian product
,
where is the vocabulary,
is the Kleene star operator,
indicates concatenation,
denotes set union, and
denotes set minus or set difference. If we do not allow the start symbol to occur in
(the word on the right side), we have to replace
by
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: