pregroup grammar

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


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

  • t lt1,tt r1t^l t \leq 1, \quad t t^r \leq 1 \quad (contraction)
  • 1tt l,1t rt1 \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,}B = \{ s, n, \dots \} of basic types (e.g. sentence and noun) and then takes the free pregroup P BP_B generated by BB. For a basic type bBb \in B, iterated adjoints ,b ll,b l,b,b r,b rr,P B\dots, b^{ll}, b^l, b, b^r, b^{rr}, \dots \in P_B are called simple types; an arbitrary type tP Bt \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 sP Bs \in P_B and the types for a sequence of words t 1,,t nP Bt_1, \dots, t_n \in P_B, is t 1t nst_1 \dots t_n \leq s?

Switching lemma (Lambek 1999): For any pair of types t,tP Bt, t' \in P_B, if ttt \leq t' then there is a type tP Bt'' \in P_B such that ttt \leq t'' without expansions and ttt'' \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 BB, the objects of the free rigid monoidal category C BC_B are the same as that of the free (quasi-)pregroup, the arrows may be described as planar string diagrams. Given two types t,tP Bt, t' \in P_B, we have that ttt \leq t' if and only if there is an arrow r:ttr : t \to t' in C BC_B.

Pregroup grammars as free rigid monoidal categories

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

L(G)={w 1w nΣ n|n,t inΔ(w i)ts}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 1w nΣ nw_1 \dots w_n \in \Sigma^n is said to be grammatical whenever there is a dictionary entry (w i,t i)Δ(w_i, t_i) \in \Delta for each word w iw_i such that t 1t nst_1 \dots t_n \leq s. One may simplify this by redefining L(G)={w 1w nΣ n|C G(w 1w n,s)}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 GC_G is the free rigid monoidal category with:

  • generating objects the disjoint union B+ΣB + \Sigma,
  • generating arrows the dictionary entries (w,t)Δ(w, t) \in \Delta with dom(w,t)=wdom(w, t) = w and cod(w,t)=tcod(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Σw \in \Sigma are omitted, hence dictionary entries are depicted as triangles with no input. Contractions are depicted as cups, e.g. from (Alice,n),(loves,n rsn l),(Bob,n)Δ(Alice, n), (loves, n^r s n^l), (Bob, n) \in \Delta and nn rsn lnsn n^r s n^l n \leq s we get the following diagram:

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

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,Σ,Δ,s)G = (B, \Sigma, \Delta, s) by defining a strong monoidal functor F:C GSF : C_G \to S, where C GC_G is the free rigid monoidal category described in section 2. SS is a suitable rigid monoidal category, e.g. FdVect\text{FdVect} or Rel\text{Rel}, depending on the application. Note the similarity with a Lawvere theory as a monoidal functor from a syntactic category to Set\text{Set}.

We require the image for all words wΣw \in \Sigma to be the monoidal unit F(w)=IF(w) = I, hence the image for each dictionary entry (w,t)Δ(w, t) \in \Delta is given by a state F(w,t):IF(t)F(w, t) : I \to F(t). The meaning F(r):IF(s)F(r) : I \to F(s) for a sentence w 1w nΣ nw_1 \dots w_n \in \Sigma^n with grammatical reduction r:w 1w nsr : w_1 \dots w_n \to s may then be computed from the individual meanings F(w i,t i):IF(t i)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)

Last revised on August 3, 2020 at 07:11:35. See the history of this page for a list of all contributions to it.