# nLab pregroup grammar

Pregroup grammar is a mathematical model of natural language grammar introduced by Lambek, it is part of the categorial grammar tradition.

## Pregroups

As defined in Lambek 1999, Lambek 2008, a pregroup is a partially-ordered monoid $(P, \leq, \cdot, 1)$ such that every object $t \in P$ has left- and right-adjoints $t^l, t^r \in P$. Explicitly we have the following four axioms:

• $t^l t \leq 1, \quad t t^r \leq 1 \quad$ (contraction)
• $1 \leq t t^l, \quad 1 \leq t^r t \quad$ (expansion)

In other words, a pregroup is a rigid monoidal category which is thin and skeletal. Note that a commutative pregroup is simply a group. Here are a few variants of pregroups that appear in the literature, see Coecke 2013:

• If we drop the anti-symmetry axiom for posets, we get a quasi-pregroup,
• If we drop the two expansion axioms, we get a protogroup.

### Free pregroups and the switching lemma

In linguistic applications, one starts with a poset $B = \{ s, n, \dots \}$ of basic types (e.g. sentence and noun) and then takes the free pregroup $P_B$ generated by $B$. For a basic type $b \in B$, iterated adjoints $\dots, b^{ll}, b^l, b, b^r, b^{rr}, \dots \in P_B$ are called simple types; an arbitrary type $t \in P_B$ may then be given as a sequence of simple types. The following lemma makes the parsing problem for free pregroups decidable — i.e. given a sentence type $s \in P_B$ and the types for a sequence of words $t_1, \dots, t_n \in P_B$, is $t_1 \dots t_n \leq s$?

Switching lemma (Lambek 1999): For any pair of types $t, t' \in P_B$, if $t \leq t'$ then there is a type $t'' \in P_B$ such that $t \leq t''$ without expansions and $t'' \leq t'$ without contractions, i.e. free protogroups recognise the same language as free pregroups.

### From pregroups to compact 2-categories

In Preller, Lambek 2007, Preller and Lambek generalise the free pregroup construction above to free compact 2-categories in order to capture proof relevance. This allows to distinguish between the distinct parsings of ambiguous phrases such as “(men and women) who like maths” vs. “men and (women who like maths)”.

Note that the compact 2-categories of Lambek and Preller differ from compact closed 2-category in that they are not required to be symmetric. A non-symmetric compact closed 2-category with one object is simply a rigid monoidal category.

Given a poset of basic types $B$, the objects of the free rigid monoidal category $C_B$ are the same as that of the free (quasi-)pregroup, the arrows may be described as planar string diagrams. Given two types $t, t' \in P_B$, we have that $t \leq t'$ if and only if there is an arrow $r : t \to t'$ in $C_B$.

## Pregroup grammars as free rigid monoidal categories

A pregroup grammar is a tuple $G = (B, \Sigma, \Delta, s)$ where $B$ and $\Sigma$ are finite sets called the basic types and the vocabulary respectively, $\Delta \subseteq \Sigma \times P_B$ is a relation called the dictionnary and $s \in P_B$ is a designated sentence type. We require that $\Delta$ is finite, i.e. the set of possible types $\Delta(w) \subseteq P_B$ is finite for each word $w \in \Sigma$. The language of $G$ is then given by:

$L(G) = \big\{ w_1 \dots w_n \in \Sigma^n \vert n \in \mathbb{N}, \quad \exists t \in \prod_{i \leq n} \Delta(w_i) \quad t \leq s \big\}$

i.e. a sequence of words $w_1 \dots w_n \in \Sigma^n$ is said to be grammatical whenever there is a dictionnary entry $(w_i, t_i) \in \Delta$ for each word $w_i$ such that $t_1 \dots t_n \leq s$. One may simplify this by redefining $L(G) = \big\{ w_1 \dots w_n \in \Sigma^n \vert C_G(w_1 \dots w_n, s) \neq \emptyset \big\}$ where $C_G$ is the free rigid monoidal category with:

• generating objects the disjoint union $B + \Sigma$,
• generating arrows the dictionnary entries $(w, t) \in \Delta$ with $dom(w, t) = w$ and $cod(w, t) = t$.

That is, a sequence of words is grammatical whenever there exists a string diagram going from the sequence of words to the sentence type. Note that traditionally the identity wires for words $w \in \Sigma$ are omitted, hence dictionnary entries are depicted as triangles with no input. Contractions are depicted as cups, e.g. from $(Alice, n), (loves, n^r s n^l), (Bob, n) \in \Delta$ and $n n^r s n^l n \leq s$ we get the following diagram:

Theorem (Buszkowski, Moroz 2008): For each pregroup grammar $G$, there is a context-free grammar $G'$ such that $L(G) = L(G')$. Furthermore, $G'$ may be computed in time polynomial in the size of $G$.

The opposite direction also holds, hence pregroup grammar and context-free grammar are said to be weakly equivalent: the translation preserves only the generated languages, it does not preserve the structure of syntax trees.

## Pregroup semantics as strong monoidal functors

One may give a semantics to a pregroup grammar $G = (B, \Sigma, \Delta, s)$ by defining a strong monoidal functor $F : C_G \to S$, where $C_G$ is the free rigid monoidal category described in section 2. $S$ is a suitable rigid monoidal category, e.g. $\text{FdVect}$ or $\text{Rel}$, depending on the application. Note the similarity with a Lawvere theory as a monoidal functor from a syntactic category to $\text{Set}$.

We require the image for all words $w \in \Sigma$ to be the monoidal unit $F(w) = I$, hence the image for each dictionnary entry $(w, t) \in \Delta$ is given by a state $F(w, t) : I \to F(t)$. The meaning $F(r) : I \to F(s)$ for a sentence $w_1 \dots w_n \in \Sigma^n$ with grammatical reduction $r : w_1 \dots w_n \to s$ may then be computed from the individual meanings $F(w_i, t_i) : I \to F(t_i)$ of the words, following Frege's principle of compositionality. This has been developed in Preller 2005 as well as in a series of papers by Bob Coecke and others, see categorical compositional distributional semantics.

• Joachim Lambek, Type Grammar Revisited, Logical Aspects of Computational Linguistics (1999)

• Anne Preller, Category Theoretical Semantics for Pregroup Grammars, Logical Aspects of Computational Linguistics, 5th International Conference, LACL 2005 (pdf)

• Anne Preller, Joachim Lambek, Free Compact 2-Categories, Mathematical Structures in Computer Science, Cambridge University Press (CUP), 2007 (pdf)

• Joachim Lambek, From Word to Sentence: A Computational Algebraic Approach to Grammar, Polimetrica 2008 (pdf)

• Wojciech Buszkowski, Katarzyna Moroz, Pregroup Grammars and Context-free Grammars, Computational Algebraic Approaches to Natural Language, Polimetrica (2008) (pdf)

• Bob Coecke, An alternative Gospel of structure: order, composition, processes, Introductory chapter to C. Heunen, M. Sadrzadeh, and E. Grefenstette. Quantum Physics and Linguistics: A Compositional, Diagrammatic Discourse. Oxford University Press, 2013 (arxiv:1307.4038)