View source for Grammar, categorial

''categorical grammar''

A type of formal grammar (cf. [[Grammar, formal|Grammar, formal]]). It can be defined as an ordered quadruple <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g0447701.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g0447702.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g0447703.png" /> are finite sets, the elements of which are called terminal symbols and elementary categories, respectively; <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g0447704.png" /> is an element of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g0447705.png" /> called the principal category; <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g0447706.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g0447707.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g0447708.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g0447709.png" /> in accordance with the following rules: 1) all elementary categories are categories; 2) if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g04477010.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g04477011.png" /> are categories, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g04477012.png" /> ( "F under Y" ) and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g04477013.png" /> ( "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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g04477014.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g04477015.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g04477016.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g04477017.png" />, then one says that the string <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g04477018.png" /> is brought into correspondence with the string <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g04477019.png" /> by the grammar <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g04477020.png" />. 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g04477021.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g04477022.png" /> by the occurrence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g04477023.png" />. If some string of categories <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g04477024.png" />, which can be brought into correspondence with the string <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g04477025.png" />, can be contracted to one category <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g04477026.png" />, and also if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g04477027.png" />, then one says that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g04477028.png" /> assigns to the string <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g04477029.png" /> the category <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g04477030.png" />. The language defined by the grammar <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g04477031.png" /> (denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g04477032.png" />) is the set of strings in the terminal symbols to which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g04477033.png" /> assigns the principal category. The category <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g04477034.png" /> (or, respectively, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g04477035.png" />) can be interpreted as an operator acting on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g04477036.png" /> from the right (from the left), the result of it being <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g04477037.png" />. The use of categorial grammars in linguistics is based on this principle. Thus, if the elementary categories are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g04477038.png" /> ( "clause" ) and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g04477039.png" /> ( "noun" ), the category <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g04477040.png" /> 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), <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g04477041.png" /> is treated as an  "intransitive verb" , etc. Here, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g04477042.png" /> 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|Grammar, context-free]]), for which the following is needed: a) to compile a non-terminal dictionary <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g04477043.png" /> consisting of those categories which are elements or parts of elements of the values of the assigning function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g04477044.png" />; b) to make <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g04477045.png" /> the initial symbol; and c) to take, as rules, all possible expressions of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g04477046.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g04477047.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g04477048.png" /> (or, correspondingly, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g04477049.png" />), and of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g04477050.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g04477051.png" />. 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|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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g04477052.png" /> a categorial grammar <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g04477053.png" /> equivalent to it (i.e. such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g04477054.png" />), and it is possible to do it so that the values of the assigning function of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g04477055.png" /> contain only categories of the type <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g04477056.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g04477057.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044770/g04477058.png" /> are elementary categories. There are also simple and substantially natural methods for obtaining a dominating grammar (cf. [[Grammar, dominating|Grammar, dominating]]) from a categorial grammar.

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[2a]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[2b]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  A.V. Gladkii,   "Formal grammars and languages" , Moscow  (1973)  (In Russian)</TD></TR></table>



====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|Formal languages and automata]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  R.H. Thomason (ed.) , ''Formal philosophy, selected papers from Richard Montague'' , Yale Univ. Press  (1974)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  J.F.A.K. van Benthem,   "Essay in logical semantics" , Reidel  (1986)</TD></TR></table>