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