Production (computer science)

A production rule (also called rule or production ) is in the theory of formal grammars a rule that specifies how produced from words by a grammar new words.


Formally, a production rule in a grammar with vocabulary, alphabet, rule set and start symbol of an element, ie.

A rule is an ordered pair of two words and if a word is a word and is off. The word may thus an arbitrarily long sequence of characters of the vocabulary to be (the Kleene hull of ) as long as it is not empty and consists not only of terminal symbols. The word can then according to the rule and replace the word can be any length, a finite string of characters in the vocabulary. In particular, consist only of terminal symbols () or the empty word be ().

A rule is often represented by the notation and a set of rules may be abbreviated by the notation.

Application of production rules

In theoretical computer science and in linguistics, the production rules of a formal grammar are used to describe formal languages ​​or to create.

If there is a word, can be a production rule to apply, with the resulting word. A word that consists only of terminal symbols, and can be derived from the start symbol, is a word of the language described by the grammar.


It is defined within a formal grammar with the nonterminal symbols and terminal symbols, the production rule. By applying this rule in the generation described by the grammar language, for example, the word to be derived word, the prefix is replaced by the conclusion. It would be according to the definition of formal grammar also possible to replace the second occurrence of the word so that the word is created.

Would also be the rule defined, the word previously considered could also be derived in the words or. (The notation used in the rule for the empty word, a word that consists of any single character. )

Computer science

As already described, provide production rules represent a fundamental part of formal grammars and therefore are used to describe formal languages. Thus, production rules are used as in the context of compiler construction to to describe a programming language. Production rules are frequently depicted here in the Backus -Naur Form.

A cognitive application have production rules in rule-based systems: This is called production rules, if the conclusions of the rules by which the system operates only consist of conjunctions of literals.


In the theory of transformational grammar illustrate production rules, which are here called phrase structure rules (PS rules), the thought that a set of gradually arises by conversion of a deep structure into a surface structure.

The first and now classic PS- rules in Chomsky's book " structures the syntax" are:

S → NP VP (one set consists of a noun phrase and a verb phrase ) VP → V NP * ( a verb phrase consists of a verb and noun phrases zero to many ) The second rule illustrates Chomsky, according to the creativity of language. A rule many (infinite ) combinations of texts can be generated. This explains why young children never heard before can say sentences; in a universal grammar, these rules were that is already innate.