Production rule

This article or the following section is not adequately provided with supporting documents ( e.g. individual evidence ). Information without sufficient evidence could be removed soon. Please help Wikipedia by researching the information and including good evidence.

A production rule (also called rule , production or replacement rule ) is in the theory of formal grammars a rule that specifies how new words or symbol sequences are produced from words through a grammar .

definition

Formally, a production rule of a grammar - with vocabulary , alphabet of terminal symbols , rule set and start symbol - an element of the set of rules, that is . ${\displaystyle p}$ ${\displaystyle G=(V,T,P,S)}$ ${\displaystyle V}$ ${\displaystyle T}$ ${\displaystyle P}$ ${\displaystyle S}$ ${\displaystyle p\in P}$

A rule is an ordered pair of the two words and when one word is off and one word is off. The word can therefore be any length of sequence of characters in the vocabulary ( is the Kleen's envelope of ), as long as it is not empty and does not only consist of terminal symbols . It is therefore . According to the rule, the word can then replace the word and can be any long, finite sequence of characters in the vocabulary. In particular, it can only consist of terminal symbols ( ) or the empty word ( ). The production rules thus represent a finite subset of the Cartesian quantity product ${\displaystyle p=(\alpha ,\beta )\in P}$ ${\displaystyle \alpha }$ ${\displaystyle \beta }$ ${\displaystyle \alpha }$ ${\displaystyle V^{*}\setminus T^{*}}$ ${\displaystyle \beta }$ ${\displaystyle V^{*}}$ ${\displaystyle \alpha }$ ${\displaystyle V}$ ${\displaystyle V^{*}}$ ${\displaystyle V}$ ${\displaystyle s\in T}$ ${\displaystyle V^{*}\setminus T^{*}=}$ ${\displaystyle V^{*}NV^{*}}$ ${\displaystyle \beta }$ ${\displaystyle \alpha }$ ${\displaystyle \beta }$ ${\displaystyle \beta \in T^{*}}$ ${\displaystyle \beta =\varepsilon }$

${\displaystyle (V^{*}\setminus T^{*})\times V^{*}=V^{*}NV^{*}\times V^{*}}$,

thus represents a relation . If one also demands that no start characters may appear on the right side of a rule, then in the above Cartesian product the right side has to appear instead . ${\displaystyle (V\setminus \{S\})^{*}}$ ${\displaystyle V^{*}}$

A rule is often represented by its notation (with the relational symbol instead of ), and the set of associated rules for each fixed can be abbreviated by the notation . ${\displaystyle p=(\alpha ,\beta )}$ ${\displaystyle \alpha \rightarrow \beta }$ ${\displaystyle \rightarrow }$ ${\displaystyle P}$ ${\displaystyle \alpha }$ ${\displaystyle \alpha \rightarrow \beta _{1},\;\alpha \rightarrow \beta _{2},\;\alpha \rightarrow \beta _{3},\ldots }$ ${\displaystyle \alpha \rightarrow \beta _{1}\;|\;\beta _{2}\;|\;\beta _{3}\;|\ldots }$

Application of production rules

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

Is a word before, this 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 that is described by the grammar. ${\displaystyle v_{1}\alpha v_{2}=v\in V^{+}}$ ${\displaystyle (\alpha ,\beta )}$ ${\displaystyle v}$ ${\displaystyle v_{1}\beta v_{2}}$

Examples

Let the production rule be defined within a formal grammar with the non-terminal symbols and the terminal symbols . By applying this rule, when generating the language described by the grammar, for example, the word can be derived from the word , with the prefix being replaced by the conclusion . However, according to the definition of formal grammars, it would also be possible to replace the second occurrence of the word so that the word arises. ${\displaystyle N=\{A,B\}}$ ${\displaystyle T=\{a,b\}}$ ${\displaystyle aBa\rightarrow bA}$ ${\displaystyle aBaBaBA}$ ${\displaystyle bABaBA}$ ${\displaystyle aBa}$ ${\displaystyle bA}$ ${\displaystyle aBa}$ ${\displaystyle aBbABA}$

If the rule were also defined, the previously considered word could also be derived into the words or . ( is the usually used notation for the empty word , a word that does not consist of a single character.) ${\displaystyle aBa\rightarrow \varepsilon }$ ${\displaystyle aBaBaBA}$ ${\displaystyle BaBA}$ ${\displaystyle aBBA}$ ${\displaystyle \varepsilon }$

Computer science

As already described, production rules are a fundamental part of formal grammars and are therefore used to describe formal languages. Production rules are used, for example, in the context of compiler construction to describe a programming language . Production rules are often presented here in the Backus-Naur form .

Production rules have a cognitive application in rule-based systems : Here one speaks of production rules if the conclusions of the rules with which the system works consist only of conjunctions of literals.

linguistics

In the theory of transformation grammar , production rules , which are called phrase structure rules ( PS rule n) here, illustrate the idea that a sentence has a grammatical structure that is built up recursively from category-bearing components . The first and classic PS rules in Chomsky's book "Structures of Syntax" are:

S → NP VP (ein Satz besteht aus einer Nominalphrase und einer Verbalphrase)
VP → V NP*　(eine Verbalphrase besteht aus einem Verb und null bis vielen Nominalphrasen)

Notes and individual references

1. ↑ The members of the crowd are referred to as non-terminal characters , to which the start character belongs, that is . ${\displaystyle N:=V\setminus T}$ ${\displaystyle S\in N}$
2. ^ Analogous to Klaus Reinhardt: Priority payer machines and the synchronization of half-track languages , Faculty of Computer Science at the University of Stuttgart; PhD thesis 1994
3. ↑ Compare the Backus-Naur form .

Web links

Wiktionary: phrase structure rule  - explanations of meanings, word origins, synonyms, translations