Arbitrary-length unambiguous buffalo sentences

Consider the well-known sentence:

Buffalo buffalo Buffalo buffalo buffalo buffalo Buffalo buffalo.

As Wikipedia explains, this is a grammatically correct sentence using the ambiguity of Buffalo (the town) and buffalo (either a noun, the animal, or a verb, "to bully"). Let me illustrate the grammatical structure of the sentence, using words from the corresponding parts of speech, and using square brackets to help the parsing:

Boston deer [(that) Seattle doves annoy] pester Austin kittens.

The Wikipedia article points out that buffalo sentences can be created with any number of repetitions of the word buffalo. For instance:

Buffalo buffalo Buffalo buffalo Buffalo buffalo buffalo buffalo buffalo.

One can easily interpret this as, e.g.,

Puppies tickle Chicago unicorns [(that) Dallas ponies [(that) squirrels mock] nag].

In other words, considering squirrels that mock Dallas ponies that nag Chicago unicorns, then there are puppies tickling such unicorns.¹ For legibility we can also write this in the following way, using Nouns, Verbs, and Cities:

N V (C N (C N (N V) V))

The problem is that this sentence can equivalently be understood as:

C N (C N (C N V) V) V

In my silly rephrasing language:

Houston birds [(that) Phoenix bunnies [(that) Memphis butterflies bother] peeve] displease.

Note that I'm allowing here an intransitive use of buffalo (or "displease" in the gloss) as a verb, which I guess is OK. (Indeed, Wikipedia claims that Buffalo! is a valid imperative sentence.)

Hence, the above buffalo sentence has the unpleasant aspect that it can be parsed in many different ways. By contrast, the original one seems to have only one reasonable parse, as long as we can rely on case to distinguish Buffalo and buffalo. Hence the simple and tantalizing question: can we construct arbitrary-length buffalo sentences that are unambiguous, i.e., have a single grammatical interpretation?²

In the rest of this post I show the following, for a certain choice of grammar which I hope covers all reasonable interpretations: for any length greater than one, the (unique) case-insensitive buffalo sentence is ambiguous; by contrast, if we are case sensitive, we can build unambiguous buffalo sentences of any length, even if we have case ambiguity on the first word.

Grammar

I will use the following grammar, in simili-BNF:

S    ->   V NPO | NP V NPO
NPO  ->   NP    | C        | ε
NP   ->   NPS   | NPS PP
NPS  ->   N     | C N
PP   ->   NP V
C    ->   Buffalo
V    ->   buffalo
N    ->   buffalo

In other words:

A sentence is either an imperative sentence or a declarative sentence, both of which have an object noun phrase.
An object noun phrase can be a noun phrase, the empty sequence (corresponding to an intransitive use of the main verb) or a single Buffalo. The last case handles the case of Buffalo buffalo Buffalo understood as "Dragonflies tease New York" (i.e., its inhabitants). I only allow Buffalo to be an object, because my understanding of grammar suggests that sentence's main verb should be "buffaloes" if Buffalo were the subject.
A noun phrase is a simple noun phrase optionally followed by a relative proposition: we will be able to nest relatives but importantly we cannot juxtapose them.
A simple noun phrase is either buffalo (the noun) or Buffalo buffalo (the city followed by the noun).
A relative proposition has a subject noun phrase and a verb, with the object of the verb being the antecedent of the proposition.

This grammar can uniquely parse the example sentence,³ and includes a few additional features not exemplified by that sentence, which I already commented about: buffalo as an imperative and/or intransitive verb, and Buffalo used as an object.

Case-insensitive case

In the fully case-insensitive case, we write everything as buffalo. As we can show, all sentences of length greater than 1 are ambiguous.

The reason is that S -> V NP and S -> NP V are two different possible parses, and it is not hard to see that we can construct NPs of arbitrary length: we can choose any number $n$ of nested PP in the derivation, and choose either N or C N at each GN, of which there are $n + 1$ . So to realize a length of $k$ , choose to create $n = ⌊ (k - 1) / 2 ⌋$ PP, and create $k - n$ words in the GN (which is between $n + 1$ and $2 (n + 1)$ ).

As an example, for buffalo buffalo buffalo buffalo buffalo, parse buffalo buffalo buffalo buffalo as NP, e.g., as, N (C N V), and parse the sentence either as V NP or NP V.

Case-sensitive case

We now assume that we can distinguish Buffalo and buffalo, except maybe for the first word, intuitively because it must carry a capital because it starts the sentence. Let us consider small lengths as examples.

For length 1, the sentence Buffalo can only be interpreted as V, namely, the imperative with no complement. My grammar forbids the declarative N, a nominal sentence declaring the existence of buffaloes, but of course this is debatable.
For length 2, Buffalo Buffalo has exactly one interpretation because the last Buffalo must clearly be a C, so the unique parse is V C. Again, we are prohibiting the nominal sentence asserting the existence of buffalo in Buffalo.
For length 3, considering Buffalo Buffalo buffalo, the first Buffalo cannot be a C as otherwise the next symbol should be buffalo, and it cannot be an N as otherwise the next Buffalo buffalo must start a PP that cannot finish. Hence the first Buffalo is a verb and we have a unique interpretation: V (C N).

For larger lengths, we will first observe that if any sequence of buffalo and Buffalo can be parsed as an PP, then there is only exactly one way to do so. To see why, observe that Buffalo must always be followed by buffalo in which case we always parse both symbols as an NPS. So write b for buffalo and b2 for Buffalo buffalo, and rewrite our sentence (uniquely) as a sequence of b's and b2's. We then see that each b or b2 at the left must pop a b at the right, so that parse fails unless the number of b and b2's is even and the rightmost half contains only b's; conversely, if this condition is satisfied, there is a unique parse. So we have proven our initial observation.

Second, we claim that for any (possibly empty) sequence S, there is at most one way to parse buffalo S or Buffalo buffalo S as an NP. This is clear as we must parse buffalo or Buffalo buffalo as an NPS and the rest as an PP, and we can then use the previous reasoning. It is not so hard to see then that this claim extends to the situation where the first symbol has ambiguous case. Indeed, for any sequence S, at most one of S and buffalo S has a successful parse as a PP (because, rewriting them using b's and b2's, only one rewriting can have an even number of symbols). Hence, for Buffalo buffalo S, only one option succeeds between parsing the initial Buffalo as an N (using case ambiguity) and buffalo S as a PP, or parsing Buffalo buffalo as an NPS and S as a PP. Likewise, for buffalo S, either we parse buffalo as an N and S as a PP, or we parse buffalo as a C (using case ambiguity): in this second case the first symbol of S cannot be Buffalo, so that, writing S as buffalo S', we parse S' as a PP. By the previous reasoning only one of these two options can succeed, and if it does then it succeeds in one unique way. So we have proven our initial claim.

We now show that for any non-empty sequence S, the only way to parse S buffalo Buffalo as a sentence is to parse S as an NP. This is because a final Buffalo is necessarily an NPO. Now, as S buffalo contains at least two symbols, it cannot be V, so it must be NP V, so the buffalo is V and we must parse S as an NP. Hence, combining this with our previous claim, for any sequence S, there is at most one way to parse the following sentences:

Buffalo S buffalo Buffalo
Buffalo buffalo S buffalo Buffalo

It is now easy to define recursively the language of sequences S that have a successful parse as a PP (or as the empty sequence $ϵ$ ), abbreviating buffalo and Buffalo as b and B. By our initial observation, such parses are then unique.

$L_{0} = ϵ$
$L_{n} = ⋃_{w \in L_{n - 1}} {b w b, B b w b}$

So using $L_{0}$ we can construct buffalo sentences with unique parses for length 3 and 4; and using the first rule in the definition of $L_{n}$ we can then reach $k + 2$ for any $k$ that we can reach. Hence, as 3 is odd, 4 is even, and 1 and 2 were previously covered, we have shown our claim: we can construct uniquely parsable buffalo sentences of any length, even with ambiguity on the case of the first word.

To illustrate, here is an example of a sentence of length 42 which we have shown to have a unique parse.⁴

Buffalo buffalo Buffalo buffalo Buffalo buffalo buffalo Buffalo buffalo Buffalo buffalo buffalo buffalo Buffalo buffalo Buffalo buffalo Buffalo buffalo Buffalo buffalo buffalo Buffalo buffalo Buffalo buffalo buffalo buffalo buffalo buffalo buffalo buffalo buffalo buffalo buffalo buffalo buffalo buffalo buffalo buffalo buffalo Buffalo.

For all animal species in the sentence, it seems semantically unclear whether the individuals are existentially or universally quantified. For instance, we do not know whether the sentence applies to all such unicorns or only some of them. ↩
By "grammatical interpretation" I mean parsing, not meaning; I am not interested in possible doubts about whether the verb buffalo means "intimidate" or "hunting buffaloes", nor do I care about which buffalo species or Buffalo city the speaker is referring to. ↩
If the initial Buffalo is V, then buffalo is an NP, we must parse a PP, Buffalo buffalo is an NP, we must parse a PP, then either we start unstacking the V and we are left with Buffalo buffalo which we cannot parse, or we further parse buffalo as an NP and then we can never unstack enough V. If the initial Buffalo is N, then for a similar reason we cannot parse what follows as a PP (if we unstack early then we are left with the second Buffalo where the verb should be), so the second buffalo is V, Buffalo buffalo is then NP, and once again we cannot parse a PP. So the initial Buffalo is C, and buffalo is then N, and Buffalo buffalo must then be a PP. We must unstack immediately, we must parse buffalo as the verb, and we have no more choices. ↩
Of course, this is just an example, and in general unique parse sentences are not themselves unique. We can in fact build unambiguous sequences following entirely different schemes; e.g., we can also show that Buffalo Buffalo buffalo w has a unique parse (with the initial Buffalo being necessarily a V), for any w in the language inductively defined by $L_{1} = {B b b}$ and $L_{n} = ⋃_{w \in F_{n - 1}} {B b B b b w b b b, B b w b}$ . ↩