production (computer science)

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, SN.

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

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.