HOME

TheInfoList



OR:

In
computer science Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
, a production or production rule is a rewrite rule that replaces some symbols with other symbols. A finite set of productions P is the main component in the specification of a
formal grammar A formal grammar is a set of Terminal and nonterminal symbols, symbols and the Production (computer science), production rules for rewriting some of them into every possible string of a formal language over an Alphabet (formal languages), alphabe ...
(specifically a
generative grammar Generative grammar is a research tradition in linguistics that aims to explain the cognitive basis of language by formulating and testing explicit models of humans' subconscious grammatical knowledge. Generative linguists, or generativists (), ...
). The other components are a finite set N of nonterminal symbols, a finite set (known as an alphabet) \Sigma of terminal symbols that is disjoint from N and a distinguished symbol S \in N that is the ''start symbol''. In an unrestricted grammar, a production is of the form u \to v, where u and v are arbitrary strings of terminals and nonterminals, and u may not be the
empty string In formal language theory, the empty string, or empty word, is the unique String (computer science), string of length zero. Formal theory Formally, a string is a finite, ordered sequence of character (symbol), characters such as letters, digits ...
. If v is the empty string, this is denoted by the symbol \epsilon, or \lambda (rather than leaving the right-hand side blank). So productions are members of the
cartesian product In mathematics, specifically set theory, the Cartesian product of two sets and , denoted , is the set of all ordered pairs where is an element of and is an element of . In terms of set-builder notation, that is A\times B = \. A table c ...
:V^*NV^* \times V^* = (V^*\setminus\Sigma^*) \times V^*, where V := N \cup \Sigma is the ''vocabulary'', ^ is the
Kleene star In mathematical logic and theoretical computer science, the Kleene star (or Kleene operator or Kleene closure) is a unary operation on a Set (mathematics), set to generate a set of all finite-length strings that are composed of zero or more repe ...
operator, V^*NV^* indicates
concatenation In formal language theory and computer programming, string concatenation is the operation of joining character strings end-to-end. For example, the concatenation of "snow" and "ball" is "snowball". In certain formalizations of concatenati ...
, \cup denotes
set union In set theory, the union (denoted by ∪) of a collection of sets is the set of all elements in the collection. It is one of the fundamental operations through which sets can be combined and related to each other. A refers to a union of ze ...
, and \setminus denotes set minus or set difference. If we do not allow the start symbol to occur in v (the word on the right side), we have to replace V^* by (V \setminus \)^* on the right side of the cartesian product symbol.See Klaus Reinhardt
Prioritatszahlerautomaten und die Synchronisation von Halbspursprachen
; Fakultät Informatik der Universität Stuttgart; 1994 (German)
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 \to (N \cup \Sigma)^*


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 a and b, with the start symbol S, and we have the following rules: : 1. S \rightarrow aSb : 2. S \rightarrow ba then we start with S, and can choose a rule to apply to it. If we choose rule 1, we replace S with aSb and obtain the string aSb. If we choose rule 1 again, we replace S with aSb and obtain the string aaSbb. This process is repeated until we only have symbols from the alphabet (i.e., a and b). If we now choose rule 2, we replace S with ba and obtain the string aababb, and are done. We can write this series of choices more briefly, using symbols: 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, \dotsc\}.


See also

*
Formal grammar A formal grammar is a set of Terminal and nonterminal symbols, symbols and the Production (computer science), production rules for rewriting some of them into every possible string of a formal language over an Alphabet (formal languages), alphabe ...
*
Finite automata A finite-state machine (FSM) or finite-state automaton (FSA, plural: ''automata''), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number ...
*
Generative grammar Generative grammar is a research tradition in linguistics that aims to explain the cognitive basis of language by formulating and testing explicit models of humans' subconscious grammatical knowledge. Generative linguists, or generativists (), ...
* L-system * Rewrite rule *
Backus–Naur form In computer science, Backus–Naur form (BNF, pronounced ), also known as Backus normal form, is a notation system for defining the Syntax (programming languages), syntax of Programming language, programming languages and other Formal language, for ...
(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

Grammar Natural language processing Formal languages