Grammar, categorial

categorical grammar

A type of formal grammar (cf. Grammar, formal). It can be defined as an ordered quadruple $ G = \langle V, W, \Phi _ {0} , f \rangle $, where $ V $ and $ W $ are finite sets, the elements of which are called terminal symbols and elementary categories, respectively; $ \Phi _ {0} $ is an element of $ W $ called the principal category; $ f $ is the assigning function, which brings each terminal symbol into correspondence with a finite set of categories — expressions formed out of the elementary categories and the syntactic symbols $ [, ] $, $ \setminus $, $ / $ in accordance with the following rules: 1) all elementary categories are categories; 2) if $ \Phi $ and $ \Psi $ are categories, then $ [ \Phi \setminus \Psi ] $( "F under Y" ) and $ [ \Phi / \Psi ] $( "F over Y" ) are categories; and 3) any category is a category either in the sense of 1) or in the sense of 2).

If $ x = a _ {1} \dots a _ {k} $, where $ a _ {i} \in V $, and $ \Phi _ {i} \in f ( a _ {i} ) $, $ i = 1 \dots k $, then one says that the string $ \Phi _ {1} \dots \Phi _ {k} $ is brought into correspondence with the string $ x $ by the grammar $ G $. It is possible to perform the operation of contraction (which will not, generally speaking, be single-valued) over a string of categories. This operation consists in successive replacement of the occurrences of substrings of the type $ \Phi [ \Phi \setminus \Psi ] $ or $ [ \Psi / \Phi ] \Phi $ by the occurrence $ \Psi $. If some string of categories $ \xi $, which can be brought into correspondence with the string $ x $, can be contracted to one category $ \Theta $, and also if $ \xi = \Theta $, then one says that $ G $ assigns to the string $ x $ the category $ \Theta $. The language defined by the grammar $ G $( denoted by $ L( G) $) is the set of strings in the terminal symbols to which $ G $ assigns the principal category. The category $ [ \Phi \setminus \Psi ] $( or, respectively, $ [ \Psi / \Phi ] $) can be interpreted as an operator acting on $ \Phi $ from the right (from the left), the result of it being $ \Psi $. The use of categorial grammars in linguistics is based on this principle. Thus, if the elementary categories are $ C $( "clause" ) and $ N $( "noun" ), the category $ [ N/N ] $ can be interpreted as "adjective" (this means that the adjective is regarded as an operator acting on a noun from the left, again yielding a noun or, more exactly, a group of nouns), $ [ N \setminus C ] $ is treated as an "intransitive verb" , etc. Here, if $ C $ is the principal category, the grammatical language thus defined consists of "regular clauses" .

A categorial grammar can be transformed into a context-free grammar (cf. Grammar, context-free), for which the following is needed: a) to compile a non-terminal dictionary $ W ^ \prime $ consisting of those categories which are elements or parts of elements of the values of the assigning function $ f $; b) to make $ \Phi _ {0} $ the initial symbol; and c) to take, as rules, all possible expressions of the form $ \Psi \rightarrow \Phi [ \Phi \setminus \Psi ] $ and $ \Psi \rightarrow [ \Psi / \Phi ] \Phi $, where $ [ \Phi \setminus \Psi ] \in W ^ \prime $( or, correspondingly, $ [ \Psi / \Phi ] \in W ^ \prime $), and of the form $ \Phi \rightarrow a $, where $ \Phi \in f( a) $. This makes it possible to bring the strings of the language defined by the grammar into correspondence with a system of components in a standard manner (cf. Grammar, context-sensitive). The subclass of the class of context-free grammars thus obtained is linguistically characterized by the fact that all its "grammatical information" is contained in the dictionary. It is possible, however, to construct for any context-free grammar $ \Gamma $ a categorial grammar $ G $ equivalent to it (i.e. such that $ L( G) = L ( \Gamma ) $), and it is possible to do it so that the values of the assigning function of $ G $ contain only categories of the type $ A, [ A \setminus B] $ and $ [ A \setminus [ B \setminus C]] $, where $ A, B, C $ are elementary categories. There are also simple and substantially natural methods for obtaining a dominating grammar (cf. Grammar, dominating) from a categorial grammar.

References

[1]	Y. Bar-Hillel, H. Gaifman, E. Shamir, "Finite-state languages: formal representations and adequacy problems" Bull. Res. Council Israel , 9, sec. F : 1 (1960) pp. 155–166
[2a]	M.I. Beletskii, "The relationship between categorical and domination grammars" Cybernetics , 5 : 4 (1969) pp. 506–512 Kibernetika (Kiev) , 5 : 4 (1969) pp. 129–135
[2b]	M.I. Beletskii, "Relationship between categorical and domination grammars II" Cybernetics , 5 : 5 (1969) pp. 540–545 Kibernetika (Kiev) , 5 : 5 (1969) pp. 10–14
[3]	A.V. Gladkii, "Formal grammars and languages" , Moscow (1973) (In Russian)

Comments

There is a remarkable increase in the interest in the subject of categorical grammars over the past years. There exists a strong connection between categorical grammars and techniques for assigning flexible types to phrases in formalized fragments of natural language. Among the calculi proposed for dealing with categorical grammars the Lambek calculus has established itself among the prominent systems. This system shows an interesting similarity to intuitionistic implicational logic.

See also Formal languages and automata.

References

[a1]	R.H. Thomason (ed.) , Formal philosophy, selected papers from Richard Montague , Yale Univ. Press (1974)
[a2]	J.F.A.K. van Benthem, "Essay in logical semantics" , Reidel (1986)