Production (computer science)

<h2 id="grammar-generation">Grammar generation</h2>
<p>To generate a string in the language, one begins with a string consisting of only a single <i>start symbol</i>, and then successively applies the rules (any number of times, in any order) to rewrite this string.  This stops when a string containing only terminals is obtained. The language consists of all the strings that can be generated in this manner.  Any particular sequence of legal choices taken during this rewriting process yields one particular string in the language. If there are multiple different ways of generating this single string, then the grammar is said to be <a href="/facts/Ambiguous_grammar/elcVDDL4">ambiguous</a>.
</p><p>For example, assume the alphabet consists of 
  
    
      
        a
      
    
    {\displaystyle a}
  
 and 
  
    
      
        b
      
    
    {\displaystyle b}
  
, with the start symbol 
  
    
      
        S
      
    
    {\displaystyle S}
  
, and we have the following rules:
</p>
1. 
  
    
      
        S
        →
        a
        S
        b
      
    
    {\displaystyle S\rightarrow aSb}

2. 
  
    
      
        S
        →
        b
        a
      
    
    {\displaystyle S\rightarrow ba}

<p>then we start with 
  
    
      
        S
      
    
    {\displaystyle S}
  
, and can choose a rule to apply to it. If we choose rule 1, we replace 
  
    
      
        S
      
    
    {\displaystyle S}
  
 with 
  
    
      
        a
        S
        b
      
    
    {\displaystyle aSb}
  
 and obtain the string 
  
    
      
        a
        S
        b
      
    
    {\displaystyle aSb}
  
. If we choose rule 1 again, we replace 
  
    
      
        S
      
    
    {\displaystyle S}
  
 with 
  
    
      
        a
        S
        b
      
    
    {\displaystyle aSb}
  
 and obtain the string 
  
    
      
        a
        a
        S
        b
        b
      
    
    {\displaystyle aaSbb}
  
. This process is repeated until we only have symbols from the alphabet (i.e., 
  
    
      
        a
      
    
    {\displaystyle a}
  
 and 
  
    
      
        b
      
    
    {\displaystyle b}
  
). If we now choose rule 2, we replace 
  
    
      
        S
      
    
    {\displaystyle S}
  
 with 
  
    
      
        b
        a
      
    
    {\displaystyle ba}
  
 and obtain the string 
  
    
      
        a
        a
        b
        a
        b
        b
      
    
    {\displaystyle aababb}
  
, and are done. We can write this series of choices more briefly, using symbols: 
  
    
      
        S
        ⇒
        a
        S
        b
        ⇒
        a
        a
        S
        b
        b
        ⇒
        a
        a
        b
        a
        b
        b
      
    
    {\displaystyle S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aababb}
  
. The language of the grammar is the set of all the strings that can be generated using this process: 
  
    
      
        {
        b
        a
        ,
        a
        b
        a
        b
        ,
        a
        a
        b
        a
        b
        b
        ,
        a
        a
        a
        b
        a
        b
        b
        b
        ,
        …
        }
      
    
    {\displaystyle \{ba,abab,aababb,aaababbb,\dotsc \}}
  
.
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Formal_grammar/QLxaQNAz">Formal grammar</a></li>
<li><a href="/facts/Finite_automata/GMusWd0a">Finite automata</a></li>
<li><a href="/facts/Generative_grammar/Pm1AMX5U">Generative grammar</a></li>
<li><a href="/facts/L-system/SGfQ416R">L-system</a></li>
<li><a href="/facts/Rewrite_rule/9PHlnnnJ">Rewrite rule</a></li>
<li><a href="/facts/Backus%E2%80%93Naur_form/xbMXDntc">Backus–Naur form</a> (A compact form for writing the productions of a context-free grammar.)</li>
<li><a href="/facts/Phrase_structure_rule/B867agmG">Phrase structure rule</a></li>
<li><a href="/facts/Post_canonical_system/7VjUe2R5">Post canonical system</a> (Emil Post's production systems- a model of computation.)</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>See Klaus Reinhardt: Prioritatszahlerautomaten und die Synchronisation von Halbspursprachen Archived 2018-01-17 at the Wayback Machine; Fakultät Informatik der Universität Stuttgart; 1994 (German) <a href="http://users.informatik.uni-halle.de/~ahyjb/dis.pdf" target="_blank">http://users.informatik.uni-halle.de/~ahyjb/dis.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
</ol>

Production (computer science) open-in-new

Production (computer science)