Namespaces
Variants
Actions

Difference between revisions of "Grammar, categorial"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
 +
<!--
 +
g0447701.png
 +
$#A+1 = 58 n = 0
 +
$#C+1 = 58 : ~/encyclopedia/old_files/data/G044/G.0404770 Grammar, categorial,
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
''categorical grammar''
 
''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).
+
A type of formal grammar (cf. [[Grammar, formal|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 <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" .
+
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|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.
+
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 $  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|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|Grammar, dominating]]) from a categorial grammar.
  
 
====References====
 
====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>
 
<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====
 
====Comments====

Latest revision as of 19:42, 5 June 2020


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)
How to Cite This Entry:
Grammar, categorial. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Grammar,_categorial&oldid=47115
This article was adapted from an original article by A.V. Gladkii (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article