30
of natural language to produce an unlimited number of parenthetical embeddings: (), (()), ((())),
and so on. A finite-state grammar cannot do justice to this common feature of natural language.
Nor is any finite-state grammar capable of producing the nested dependencies found in predicate
logic. In the sentence “Someone is liked by everyone,” a universal quantifier lies in the scope of
an existential quantifier. The ability of the grammar of predicate logic to produce this sort of
structure cannot be represented by a finite-state grammar.
One might want to object to Chomsky by pointing out that there are limits on how much
recursive embedding a person can process. At least on first hearing, one is stunned by a sentence
like “That that that that Jim likes guns is troubling is not surprising is worthy of reflection is
pretty likely.” Might these limits show that the grammar represented in the brain is finite-state
after all? One must distinguish, however, between the sort of grammar represented in the
mind/brain versus limits on one’s memory capacity. The initial puzzlement at such a sentence
reflects one’s incapacity to remember all of the elements while first reading it. It does not reflect
the nature of the grammar represented.
A phrase-structure grammar, although still not adequate for natural language, is
dramatically more powerful than a finite-state grammar. A phrase structure grammar consists of
rules indicating the possible structures of a given type of phrase, e.g. that a sentence may consist
of a noun phrase and a verb phrase, that a verb phrase may consist of a verb followed by a noun
phrase. And so on. A phrase-structure grammar allows for recursive embedding since each
phrase can be analyzed into constituent phrases which are themselves further analyzable
potentially ad infinitum.
Finite-state grammars require simpler computations than do any type of phrase-structure
grammar, since the former are limited to local dependencies. Phrase-structure grammars require
greater computational sophistication, namely that the system represent long-distance hierarchical