There's been a lot of discussion recently in the popular press and in the blogosphere about Timothy Q. Gentner, Kimberly M. Fenn, Daniel Margoliash & Howard C. Nusbaum, "Recursive syntactic pattern learning by songbirds", Nature, 27 April 2006.) (Also see Gary Marcus, "Startling Starlings", Nature, 27 April 2006.)
What's said to be at issue here is whether "European starlings (Sturnus vulgaris) accurately recognize acoustic patterns defined by a recursive, self-embedding, context-free grammar." The background for this question is a hypothesis about human linguistic abilities, which Gentner et al. describe this way:
Humans regularly produce new utterances that are understood by other members of the same language community. Linguistic theories account for this ability through the use of syntactic rules (or generative grammars) that describe the acceptable structure of utterances. The recursive, hierarchical embedding of language units (for example, words or phrases within shorter sentences) that is part of the ability to construct new utterances minimally requires a ‘context-free’ grammar that is more complex than the ‘finite-state’ grammars thought sufficient to specify the structure of all non-human communication signals. Recent hypotheses make the central claim that the capacity for syntactic recursion forms the computational core of a uniquely human language faculty.
Specifically, Gentner et al. are challenging the interpretation of a paper by Tecumseh Fitch and Marc Hauser, "Computatational Constraints on Syntactic Processing in a Nonhuman Primate", Science, January 16, 2004 (discussed in Language Log here). Fitch and Hauser claimed to show that humans are able to handle a kind of grammar called context-free, whereas cotton-top tamarins can't do this, but can only handle finite-state grammars. In previous posts, I've been highly skeptical of Fitch and Hauser's interpretation of their results:
Hi Lo, Hi Lo, it's off to formal language theory we go (1/17/2004)
Humans context-free, monkeys finite-state? Apparently not. (8/31/2004)
Homo hemingwayensis (01/09/2005)
Rhyme schemes, texture discrimination and monkey syntax (02/09/2006)
Learnable and unlearnable patterns -- of what? (02/25/2006)
So I'm not surprised to learn that Gentner et al. were able to teach starlings the kind of patterns that Fitch and Hauser failed to teach monkeys. However, I don't think that Gentner's success tells us any more about grammatical abilities (or the lack of them) than Fitch and Hauser's failure did.
That's not because I think that these experiments were badly executed, or that their results are not interesting. There are two key problems, in my opinion.
First, we're asked to evaluate the claim that a creature does or doesn't have the ability to process types of sequences (conceptually) requiring an unbounded number of states, on the basis of experiments that deal with a small number of short sequences. Any competent computer science undergraduate can set up a finite automaton that can process the sequences used in these papers; and if she's taken a machine learning course, she should be able to set up several sorts of models that can learn the distinctions in question, without being able to deal with general context-free or "embedding" languages at all. (See here and here for some discussions of one way to approach this.)
And second, if we make a serious attempt to investigate what it would be like to have the ability to process general context-free languages, even in the case of fairly short strings, we will quickly find that humans fail the test, at least if we approach the problem in the way that Fitch, Hauser, Genter et al. have done.
I'll try to explain and exemplify this in a minute, but first let me temper the generally skeptical tone of this and previous posts on the subject. I do believe that (most?) human languages genuinely involve recursive embedding; and I think it's quite possible that some types of birdsong, like some other sorts of animal activity, also involve embedding of "plans within plans", though perhaps not recursion in the strict sense of some type of unit forming part of another unit of the same type. I also think that experiments like these are well worth doing, and are likely to lead to some real insights about biological pattern processing.
However, I remain skeptical that such experiments are telling us which animals can process what type of grammar. To see why, let's start with the most basic and simplest context-free language, the Dyck language. As the Wikipedia explains:
In the theory of formal languages of computer science, mathematics, and linguistics, the Dyck language (Dyck being pronounced "deek") is the language consisting of those balanced strings of parentheses [ and ].
Sentences of this Dyck language include [], [][], [[]], [[][]], and so on.
Trivially, no strings starting with ] or ending with [ are in the Dyck language. And slightly less trivially, the Dyck language excludes strings like []] and [[] in which the number of [ and ] aren't equal.
Finally, strings with equal numbers of opens and closes are excluded if (as you scan from left to right through the string) a ] ever occurs when there is no earlier unmatched [. Another way to think about this is that as you scan from left to right, you add 1 to a total whenever you see [, and subtract 1 whenever you see ]. If the total is always non-negative as you scan through the string, and is zero at the end, then the string is in this Dyck language. Otherwise it isn't.
Actually, the situation is just a little more complicated: in the general case, a Dyck language can have more than one pair of matching types of parentheses. You could represent these as being like ( ), { }, < >, etc., but the most general way to think of them as parentheses or brackets indexed by integers, e.g. [1 ]1 , [2 ]2, [3 ]3, etc. Each type of parentheses in a Dyck language needs to match up pairwise in just the same way that a single type of parentheses does.
Now, Dyck languages are a simple and obvious case of string-sets that can't be handled by a "finite automaton". The "non-finite" aspect here is that you might need to count up an arbitrary number of left parens before counting down the same number of right parens. You can try to handle that by setting up a state that means "I need to find one right paren", and another state that means "OK, now I need to find two right parens", and another state that means "now we need three right parens", and so on. That will work as long as the input never stacks up more left parens than than the number of states you've set up -- but the number of left parens that might occur in the input is not bounded. (Though to handle a Dyck language with one kind of parenthesis and strings no longer than six, you'd only need three states, etc...)
In fact, Dyck languages have a special relationship to the general class of context-free languages. I'll remind the techies in the audience that according to the Chomsky-Schützenberg theorem, every context-free language can be represented as a homomorphism of the intersection of a regular language and a Dyck language. For everybody else, let's just say that any critter that can handle context-free languages in general ought to be able to deal with Dyck languages.
But anyone who has ever written a computer program knows that it's not trivial for humans to keep track of balancing parentheses. Quick, tell me whether the parentheses in this expression balance or not:
(*p == c && (prop1(*(p+1)) || prop2(*(p+1))))
It's hard to tell -- and that's why many text editors for programmers flash the corresponding left parenthesis when you type a right parenthesis, or offer other forms of paren-tracking help.
It's no easier for humans to keep track of a Dyck language in acoustic rather than textual form. To illustrate this, I've written a little program that will map parenthesis-language strings onto sequences of two pitches -- e and c, if you're keeping track musically. Consider the higher pitch to represent an open parenthesis, and the lower pitch to represent a close parenthesis. Then you can listen to a sequence of such strings, and ask yourself whether each string is in the Dyck language or not.
Go ahead, try it:
Let me make it easier for you. The sequence above either (a) starts out with a sequence of Dyck-language strings, and ends with a sequence of non-Dyck-language strings; or (b) starts with a sequence of non-Dyck strings, and ends with a sequence of Dyck strings. So all you need to do is to get used to whatever the pattern is when the music starts, and raise your hand when the grammar changes :-).
Consider yourself a starling, or a cotton-top tamarin, and try it again.
If you're like every other human I've tested, you find this task pretty hard. If you're quick and you care enough, you can count on your mental fingers, so to speak, adding one for each higher pitch and subtracting one for each lower pitch, and "parse" the sequence that way. But the difference between the Dyck and non-Dyck patterns is not, in the general case, cognitively salient to humans without intellectual scrutiny. In contrast, we don't need to count on our mental fingers to understand the structures of real spoken language. And I'd be astounded if the difference between Dyck and non-Dyck strings is cognitively salient to starlings or to any other animals either.
That doesn't mean that human languages shouldn't analyzed in terms of something like context-free grammars. Nor does it tell us whether starlings' songs should be so analyzed. But I think it indicates that the ability to learn to discriminate auditory patterns generated by different sorts of grammars is probably not a reliable indication of what sorts of grammatical generation and analysis animals employ in natural, ecologically valid activities. At least, if this type of pattern-discrimination is the criterion, then humans can't handle context-free grammars either.
FYI, the "score" for the little musical interlude linked above is here:
[[[]]]][[]]
[][[[]][]]
[[[]]]]]][]
[][[[][[[[[]
[[[[[]][[[]
[[[[][[[]]
[[[[[]]]]]
[[]]][][[[]
[[]][[[][]
[[]][[[]]]]
[]][[]]]]]]
[]]][][]][[][[][[[]
[][]][[][]][]
[][[[][[[]]]]][]
[]]]]][[][]]
[][][[][]]
[[]]]][]][][][[]]]
[[[[[]][[][]
[]][]]]][[]][]]]][[][][[]
[][[][][]]
[[]]]]][]]]
[][[][[]][]]
[[[][][]][]]
[][[]][]
[][[][][[]][[][]][]]
[[][[]]]
[][[]][[]][]
[[[][][]]]
[[]][[][]]
[[[][][][]]][]
[][][][][]
[][][[][]]
[[][]][[]]
[[[[[][[]]]]]]
I created the midi file using the terrific free software program keykit, using a couple of trivial little programs to generate random Dyck strings and random finite-state strings over the same alphabet, and to map them to keykit inputs. If anyone wants the programs to make stimuli for some real experiments, let me know. But I'm willing to place a bet in advance on how the experiments will come out...
[Some earlier Language Log posts on related topics:
Language in Humans and Monkeys (01/16/2004)
Hi Lo, Hi Lo, it's off to formal language theory we go (1/17/2004)
Cotton-top tamarins: on the road to phonology as well as syntax? (02/09/2004)
Humans context-free, monkeys finite-state? Apparently not. (8/31/2004)
Homo hemingwayensis (01/09/2005)
JP versus FHC+CHF versus PJ versus HCF(08/25/2005)
Rhyme schemes, texture discrimination and monkey syntax (02/09/2006)
Learnable and unlearnable patterns -- of what? (02/25/2006) ]
[Update: Noam Chomsky is quoted here as asserting that "[t]he [Gentner] article is based on an elementary mathematical error" and that "[i]t has nothing remotely to do with language; probably just with short-term memory". It's not clear why he didn't offer similar views on the Fitch and Hauser paper; perhaps no one asked him at the time, or perhaps he liked its conclusions better. I guess it's conceivable that he thinks that Gentner et al. committed "an elementary mathematical error" while Fitch and Hauser didn't, and that Gentner et al. are just studying short-term memory while Fitch and Hauser were studying language learning; but it's hard for me to see how he could hold that view.]
Posted by Mark Liberman at April 27, 2006 10:24 PM