
This article needs additional citations for verification.(November 2012) |
A production or production rule in computer science is a rewrite rule specifying a symbol substitution that can be recursively performed to generate new symbol sequences. A finite set of productions is the main component in the specification of a formal grammar (specifically a generative grammar). The other components are a finite set of nonterminal symbols, a finite set (known as an alphabet) of terminal symbols that is disjoint from and a distinguished symbol that is the start symbol.
In an unrestricted grammar, a production is of the form , where and are arbitrary strings of terminals and nonterminals, and may not be the empty string. If is the empty string, this is denoted by the symbol , or (rather than leaving the right-hand side blank). So productions are members of the cartesian product
- ,
where is the vocabulary, is the Kleene star operator, indicates concatenation, denotes set union, and denotes set minus or set difference. If we do not allow the start symbol to occur in (the word on the right side), we have to replace by on the right side of the cartesian product symbol.
The other types of formal grammar in the Chomsky hierarchy impose additional restrictions on what constitutes a production. Notably in a context-free grammar, the left-hand side of a production must be a single nonterminal symbol. So productions are of the form:
Grammar generation
To generate a string in the language, one begins with a string consisting of only a single start symbol, and then successively applies the rules (any number of times, in any order) to rewrite this string. This stops when a string containing only terminals is obtained. The language consists of all the strings that can be generated in this manner. Any particular sequence of legal choices taken during this rewriting process yields one particular string in the language. If there are multiple different ways of generating this single string, then the grammar is said to be ambiguous.
For example, assume the alphabet consists of and
, with the start symbol
, and we have the following rules:
- 1.
- 2.
then we start with , and can choose a rule to apply to it. If we choose rule 1, we replace
with
and obtain the string
. If we choose rule 1 again, we replace
with
and obtain the string
. This process is repeated until we only have symbols from the alphabet (i.e.,
and
). If we now choose rule 2, we replace
with
and obtain the string
, and are done. We can write this series of choices more briefly, using symbols:
. The language of the grammar is the set of all the strings that can be generated using this process:
.
See also
- Formal grammar
- Finite automata
- Generative grammar
- L-system
- Rewrite rule
- Backus–Naur form (A compact form for writing the productions of a context-free grammar.)
- Phrase structure rule
- Post canonical system (Emil Post's production systems- a model of computation.)
References
- See Klaus Reinhardt: Prioritatszahlerautomaten und die Synchronisation von Halbspursprachen Archived 2018-01-17 at the Wayback Machine; Fakultät Informatik der Universität Stuttgart; 1994 (German)
This article needs additional citations for verification Please help improve this article by adding citations to reliable sources Unsourced material may be challenged and removed Find sources Production computer science news newspapers books scholar JSTOR November 2012 Learn how and when to remove this message A production or production rule in computer science is a rewrite rule specifying a symbol substitution that can be recursively performed to generate new symbol sequences A finite set of productions P displaystyle P is the main component in the specification of a formal grammar specifically a generative grammar The other components are a finite set N displaystyle N of nonterminal symbols a finite set known as an alphabet S displaystyle Sigma of terminal symbols that is disjoint from N displaystyle N and a distinguished symbol S N displaystyle S in N that is the start symbol In an unrestricted grammar a production is of the form u v displaystyle u to v where u displaystyle u and v displaystyle v are arbitrary strings of terminals and nonterminals and u displaystyle u may not be the empty string If v displaystyle v is the empty string this is denoted by the symbol ϵ displaystyle epsilon or l displaystyle lambda rather than leaving the right hand side blank So productions are members of the cartesian product V NV V V S V displaystyle V NV times V V setminus Sigma times V where V N S displaystyle V N cup Sigma is the vocabulary displaystyle is the Kleene star operator V NV displaystyle V NV indicates concatenation displaystyle cup denotes set union and displaystyle setminus denotes set minus or set difference If we do not allow the start symbol to occur in v displaystyle v the word on the right side we have to replace V displaystyle V by V S displaystyle V setminus S on the right side of the cartesian product symbol The other types of formal grammar in the Chomsky hierarchy impose additional restrictions on what constitutes a production Notably in a context free grammar the left hand side of a production must be a single nonterminal symbol So productions are of the form N N S displaystyle N to N cup Sigma Grammar generationTo generate a string in the language one begins with a string consisting of only a single start symbol and then successively applies the rules any number of times in any order to rewrite this string This stops when a string containing only terminals is obtained The language consists of all the strings that can be generated in this manner Any particular sequence of legal choices taken during this rewriting process yields one particular string in the language If there are multiple different ways of generating this single string then the grammar is said to be ambiguous For example assume the alphabet consists of a displaystyle a and b displaystyle b with the start symbol S displaystyle S and we have the following rules 1 S aSb displaystyle S rightarrow aSb 2 S ba displaystyle S rightarrow ba then we start with S displaystyle S and can choose a rule to apply to it If we choose rule 1 we replace S displaystyle S with aSb displaystyle aSb and obtain the string aSb displaystyle aSb If we choose rule 1 again we replace S displaystyle S with aSb displaystyle aSb and obtain the string aaSbb displaystyle aaSbb This process is repeated until we only have symbols from the alphabet i e a displaystyle a and b displaystyle b If we now choose rule 2 we replace S displaystyle S with ba displaystyle ba and obtain the string aababb displaystyle aababb and are done We can write this series of choices more briefly using symbols S aSb aaSbb aababb displaystyle S Rightarrow aSb Rightarrow aaSbb Rightarrow aababb The language of the grammar is the set of all the strings that can be generated using this process ba abab aababb aaababbb displaystyle ba abab aababb aaababbb dotsc See alsoFormal grammar Finite automata Generative grammar L system Rewrite rule Backus Naur form A compact form for writing the productions of a context free grammar Phrase structure rule Post canonical system Emil Post s production systems a model of computation ReferencesSee Klaus Reinhardt Prioritatszahlerautomaten und die Synchronisation von Halbspursprachen Archived 2018 01 17 at the Wayback Machine Fakultat Informatik der Universitat Stuttgart 1994 German