A type of formal grammar (cf. Grammar, formal); actually it is a special case of a Post calculus (see Post canonical system). A systematic study of this grammar was begun in the 1950s by N. Chomsky, who pointed out its applications to linguistics and isolated the classes of generative grammars which are most important to applications — context-sensitive grammars, context-free grammars, regular grammars (cf. Grammar, context-sensitive; Grammar, context-free; Grammar, regular). These classes proved to be especially interesting from the mathematical point of view.

A generative grammar is an ordered quadruple , where and are disjoint finite sets, known, respectively, as the terminal and non-terminal alphabets, or dictionaries (their elements are called, respectively, terminal, or basic, and non-terminal, or auxiliary, symbols), is an element of called the initial symbol, and is a finite set of rules of the form , where and are strings (words, cf. Word) over the alphabet and forms no part of ; is called the scheme of the grammar. If two strings and can be represented as, respectively, , , where is one of the rules of , then one says that is directly derivable from in (denoted by or ). A sequence of strings is said to be a derivation of from in if for all , , ; the number is the length of the derivation. A derivation is said to be complete if and does not contain non-terminal symbols. If there exists a derivation of a string from a string in , then is said to be derivable from in . The set of strings in the terminal alphabet that are derivable in from is said to be the language generated by the grammar (denoted by ). Two generative grammars are equivalent if they generate the same language. The class of languages generated by all possible generative grammars coincides with the class of recursively-enumerable sets of strings.

The so-called complexity functions, the most important ones being time complexity and space complexity, are used to estimate the complexity of a derivation in generative grammars. The time complexity of a grammar is a function of a natural argument, the value of which for each is equal to the smallest number having the following property: For any string such that (where is the length of ) there exists a derivation of this chain from the initial symbol of with length at most ; if there are no strings such that and , then . The space complexity of the grammar is defined in an analogous manner by replacing the length of a derivation by the greatest length of the strings , .

Let be some set of complete derivations in the grammar and let be the set of terminal strings of derivations belonging to ; then . If is effectively given, then one says that a certain way of controlling a derivation in has been given. A study of the ways of controlling a derivation is material in applications, since the possibility of using certain definite derivations rather than random ones corresponds to the situation which occurs in natural language. Control of a derivation can be realized, in particular, by imposing restrictions on the sequence of rules used in the derivation (e.g. the set of  "admissible"  sequences of rules may itself be generated by some generative grammar ; in such a case the language is defined by an ordered pair of generative grammars , which is called a generalized grammar), either on the strings constituting the derivation or by some more complicated method (e.g. the rule employed in a subsequent stage may depend on the type of the string obtained in the preceding stage).

Studies of generative grammars necessarily involve algorithmic problems. If is a property of languages, is a decidable class of grammars, and if there exists an algorithm which allows one to decide, for any grammar , whether or not the language has the property , then one says that is decidable in the class . In the class of all generative grammars no non-trivial property (i.e. such that the corresponding class of languages contains both languages which display and languages which do not display this property) is decidable. One may speak, in a similar manner, about relations which are decidable in a certain class of grammars. There also arise problems of a different type, e.g. the existence, for a given grammar , of an algorithm by which it is possible to find, from any strings in its terminal alphabet, the value of a given predicate for , . In particular, if denotes , then one is asking for an algorithm for recognizing if an arbitrary string forms part of the language . If such an algorithm in fact exists for the grammar , then the problem of its complexity — or, in other words, of the recognition complexity of the language — is important.

See also Grammar, context-sensitive; Grammar, context-free; Grammar, linear; Grammar, regular; Mathematical linguistics.

References

See also Formal languages and automata.

For a survey of the topic  "controlling a derivation"  see [a1], Chapt. 5.

References