The Weak Generative Capacity of Parenthesis-Free Categorial Grammars

The Weak Generative Capacity of Parenthesls-Free Categorial Gramnmrs Joyce Friedman, Dawci Dai and Weiguo Wang Computer Science Department, Boston University Ill Cummlngton Street, Boston, Ma~ssachusetts 02215, U. S. A. Abstract: We study the weak generative capacity of a class of parenthesis-free categorial grammars derived /torn those of Aries and Steedman by varying the set of reduction rules. With forward cancellation as the only rule, the grammars are weakly equivalent to context-free grammars. When a back- ward combination rule is added, it is no longer possible to oh- lain all the context-free languages. With suitable restriction of the forward partial rule, the languages are still context-free and a push-down automaton can be used for recognition. Us- ing the unrestricted rule of forward partial combination, a context-sensitive language is obtained. INTRODUCTION The system of categorial grammars, developed ill lnodern times from the work of Ajdukiewicz (1935), has recently been the attention of renewed interest, hlspired by the use of categori-- al notions in Montague gramlnar~ more recent systems, sneh as GPSC, have developed related corlccpts and notations. This in turn leads to a resurgence of interest in pure catcgorial systems. Classically, a categorial grammar is a quadruple G(VT, VA,J;,F), where VT is a finite set of morl)hemes , and VA is a tinite set of atomic categories, one of which is the distinguished category S. The set CA of categories is formed from VA as follows: (1) VAisasubset of CA, (2) if X and Y are in CA, t.hcJ, (X,"Y)is I CA The grammar also (:md.ain,~ a lexicon F, which is a function from words to finite subsets of CA. A categorial grammar lacks rules; instead there is a can cellation ride mq)lieit ill the formalism: if X and Y are categories, then (X/Y) Y -' X. The lauguage of a categorial grammar is the set of ter minal strings with corresponding category symbol strings reducible by cancellation to the sentence symbol S. In [1] Ades and Steedman offer a form of categorial grammar in which some of the notations and concepts of the usual categorial grammar are modified. The formalism at first appears to be more powerful, because in addition to tile cancellation rule there are several other metarutes. IIowever, on closer ex amination there are other reasons to suspecl, that tile resulting language class (lifters sharply from that of the traditional grammars. Among the new rules, the forward partial rule (FI) rule) is most interesting, since one may immediately conchlde that this rule leads to a very large number of possible parsings of any sentence (almost equal to the number of different binary trees of n leaves if the length of the sentence is n). But its effects on the generative power of categorial grammar are not really obvious and immediate. Ades and Steedman raised the question in the foot- note 7 in [1] and left it unanswered. We will first formally define categorial grammar and the associated concepts. Then we analyze the generative power of the categoriat gralnmars with …

Content truncated to 500 words