Production (computer science)

A production or production rule in <a href="/facts/Computer_science/lN3pEyPz">computer science</a> is a <a href="/facts/Rewrite_rule/9PHlnnnJ">rewrite rule</a> specifying a symbol substitution that can be <a href="/facts/Recursion_(computer_science)/2uXo18Gv">recursively</a> performed to generate new symbol sequences. A finite set of productions 
 
 
 
 P
 
 
 {\displaystyle P}
 
 is the main component in the specification of a <a href="/facts/Formal_grammar/QLxaQNAz">formal grammar</a> (specifically a <a href="/facts/Generative_grammar/Pm1AMX5U">generative grammar</a>). The other components are a finite set 
 
 
 
 N
 
 
 {\displaystyle N}
 
 of <a href="/facts/Nonterminal_symbol/3BLz2wJU">nonterminal symbols</a>, a finite set (known as an alphabet) 
 
 
 
 Σ
 
 
 {\displaystyle \Sigma }
 
 of <a href="/facts/Terminal_symbol/3BLz2wJU">terminal symbols</a> that is <a href="/facts/Disjoint_sets/nLr8XRVd">disjoint</a> from 
 
 
 
 N
 
 
 {\displaystyle N}
 
 and a distinguished symbol 
 
 
 
 S
 ∈
 N
 
 
 {\displaystyle S\in N}
 
 that is the start symbol.
In an <a href="/facts/Unrestricted_grammar/u9mR49Dc">unrestricted grammar</a>, a production is of the form 
 
 
 
 u
 →
 v
 
 
 {\displaystyle u\to v}
 
, where 
 
 
 
 u
 
 
 {\displaystyle u}
 
 and 
 
 
 
 v
 
 
 {\displaystyle v}
 
 are arbitrary strings of terminals and nonterminals, and 
 
 
 
 u
 
 
 {\displaystyle u}
 
 may not be the <a href="/facts/Empty_string/T7udJlmQ">empty string</a>. If 
 
 
 
 v
 
 
 {\displaystyle v}
 
 is the empty string, this is denoted by the symbol 
 
 
 
 ϵ
 
 
 {\displaystyle \epsilon }
 
, or 
 
 
 
 λ
 
 
 {\displaystyle \lambda }
 
 (rather than leaving the right-hand side blank). So productions are members of the <a href="/facts/Cartesian_product/BfqBWzdL">cartesian product</a>

V
 
 ∗
 
 
 N
 
 V
 
 ∗
 
 
 ×
 
 V
 
 ∗
 
 
 =
 (
 
 V
 
 ∗
 
 
 ∖
 
 Σ
 
 ∗
 
 
 )
 ×
 
 V
 
 ∗
 
 
 
 
 {\displaystyle V^{*}NV^{*}\times V^{*}=(V^{*}\setminus \Sigma ^{*})\times V^{*}}
 
,
where 
 
 
 
 V
 :=
 N
 ∪
 Σ
 
 
 {\displaystyle V:=N\cup \Sigma }
 
 is the vocabulary,

∗
 
 
 
 
 {\displaystyle {}^{*}}
 
 is the <a href="/facts/Kleene_star/I6SX0f2Y">Kleene star</a> operator, 
 
 
 
 
 V
 
 ∗
 
 
 N
 
 V
 
 ∗
 
 
 
 
 {\displaystyle V^{*}NV^{*}}
 
 indicates <a href="/facts/Concatenation/1npYg6rc">concatenation</a>, 
 
 
 
 ∪
 
 
 {\displaystyle \cup }
 
 denotes <a href="/facts/Union_(set_theory)/KVVXKfWl">set union</a>, and 
 
 
 
 ∖
 
 
 {\displaystyle \setminus }
 
 denotes <a href="/facts/Complement_(set_theory)/yWUePIYY">set minus or set difference</a>. If we do not allow the start symbol to occur in 
 
 
 
 v
 
 
 {\displaystyle v}
 
 (the word on the right side), we have to replace 
 
 
 
 
 V
 
 ∗
 
 
 
 
 {\displaystyle V^{*}}
 
 by 
 
 
 
 (
 V
 ∖
 {
 S
 }
 
 )
 
 ∗
 
 
 
 
 {\displaystyle (V\setminus \{S\})^{*}}
 
 on the right side of the cartesian product symbol.
The other types of formal grammar in the <a href="/facts/Chomsky_hierarchy/tUYCL00R">Chomsky hierarchy</a> impose additional restrictions on what constitutes a production. Notably in a <a href="/facts/Context-free_grammar/yu1FFdK4">context-free grammar</a>, the left-hand side of a production must be a single nonterminal symbol. So productions are of the form:

N
        →
        (
        N
        ∪
        Σ
        
          )
          
            ∗
          
        
      
    
    {\displaystyle N\to (N\cup \Sigma )^{*}}

Production (computer science) open-in-new

Production (computer science)