In computer science, productions, also called production rules, are the primary way of defining a formal grammar. A production rule specifies how symbol substitution can be recursively performed on a sequence of symbols to produce a new sequence of symbols. The components for defining a grammar include a set of production rules *P*, a finite set *N* of nonterminal symbols, a finite set of symbols Σ, known as the alphabet, which is disjoint of *N*, and finally a start symbol *S* that belongs to *N*, *S*∈*N*.

In an unrestricted grammar, Type-0 of the Chomsky Hierarchy, a production is denoted *u* →*v*, where *u* and *v* are arbitrary strings and can be either nonterminals or terminals although *u* cannot be the empty string. v, however, can be the empty string as denoted as either ε or λ.

Unrestricted grammar productions are of the form:

(N ∪ Σ)*N(N ∪ Σ)* → (N ∪ Σ)*

Other grammars in the Chomsky Hierarchy are more restrictive. For example, context free grammars (Type-2) only allow a single, nonterminal symbol on the left hand side of the production. So those productions are of the form:

N →(N ∪ Σ)*

Starting with a single start symbol and then applying the production rules in any order until a string with only terminals is created is the method by which to create a string in the language. The language therefore consists of all strings generated in this manner. Any possible sequence of productions that lead from a start symbol to a string of terminals is valid. A grammar is considered ambiguous if there is more than one possible sequence of productions to create any string.

« Back to Glossary Index