15.2.2 Are English and Other Natural Languages Regular Languages?

"How's business?" I asked.

“Lousy and terrible.” Fritz grinned richly. “Or I pull off a new deal in the next month or I go as a gigolo,”

“Either … or …,” I corrected, from force of professional habit.

“I’m speaking a lousy English just now,” drawled Fritz, with great self-satisfaction. “Sally says maybe she’ll give me a few lessons.”

Christopher Isherwood, “Sally Bowles”, from Goodbye to Berlin. 1935

Consider a formal version of the English language modeled as a set of strings of words. Is this language a regular language? It is generally agreed that natural languages like English, viewed in this way, are not regular, although most attempted proofs of this are well-known to be incorrect.

One kind of argument that is often made informally is that English number agreement cannot be captured by a regular grammar, because of the potentially unbounded distance between the subject and the verb in sentences like these:

(15.1) Which problem did your professor say she thought was unsolvable?

(15.2) Which problems did your professor say she thought were unsolvable?

In fact, a simple regular grammar can model number agreement, as Pullum and Gazdar (1982) show. Here's their regular (right-linear) grammar that models these sentences:

S $ \rightarrow $ Which problem did your professor say T

S $ \rightarrow $ Which problems did your professor say U

T $ \rightarrow $ she thought T | you thought T | was unsolvable

U $ \rightarrow $ she thought U | you thought U | were unsolvable

So a regular grammar could model English agreement. This grammar isn't elegant, and would have a huge explosion in the number of grammar rules, but that's not relevant to the question of the regularity or non-regularity of English.

Another common flaw with previously attempted proofs, pointed out by Mohri and Sproat (1998), is that the fact that a language $ L $ contains a subset $ L' $ at position $ P' $ in the Chomsky hierarchy does not imply that the language $ L $ is also at position $ P' $. For example, a regular language can contain as a proper subset a context-free language. Thus the following two languages are context-free

$$ L_{1}=\{a^{n} b^{n}:n\in N\} $$

$$ L_2 = \{ w w^R : w \in \Sigma^ * \} $$

and yet both $ L_{1} $ and $ L_{2} $ are contained in the regular language L:

$$ L=\{a^{p} b^{q}:p,q\in N\} $$

Thus, the fact that a language L contains a sublanguage that is very complex says nothing about the overall complexity of language L.

There are correct proofs that English (or rather “the set of strings of English words considered as a formal language”) is not a regular language, based on the pumping lemma. A proof by Partee et al. (1990), for example, is based on a famous class of sentences with center-embedded structures (Yngve, 1960); here is a variant of these sentences:

The cat likes tuna fish.

The cat the dog chased likes tuna fish.

The cat the dog the rat bit chased likes tuna fish.

The cat the dog the rat the elephant admired bit chased likes tuna fish.

These sentences get harder to understand as they get more complex. For now, let's assume that the grammar of English allows an indefinite number of embeddings. Then in order to show that English is not regular, we need to show that languages with sentences like these are isomorphic to some non-regular language. Since every fronted NP must have its associated verb, these sentences are of the form:

(the + noun) $ ^n $ (transitive verb) $ ^{n-1} $ likes tuna fish.

The idea of the proof will be to show that sentences of these structures can be produced by intersecting English with a regular expression. We will then use the pumping lemma to prove that the resulting language isn't regular.

In order to build a simple regular expression that we can intersect with English to produce these sentences, we define regular expressions for the noun groups (A) and the verbs (B):

A = { the cat, the dog, the rat, the elephant, the kangaroo,... }

B = { chased, bit, admired, ate, befriended, ... }

Now if we take the regular expression /A* B* likes tuna fish/ and intersect it with English (considered as a set of strings), the resulting language is:

$$ L=x^{n}y^{n-1}\text{likes}tuna\text{fish},x\in A,y\in B $$

This language L can be shown to be non-regular via the pumping lemma (see Exercise 15.2). Since the intersection of English with a regular language is not a regular language, English cannot be a regular language either (since the regular languages are closed under intersection).

There is a well-known flaw, or at least an overly strong assumption with this proof, which is the assumption that these structures can be nested indefinitely. Sentences of English are clearly bounded by some finite length; perhaps we can safely say that all sentences of English are less than a billion words long. If the set of sentences is finite, then all natural languages are clearly finite-state. This is a flaw with all such proofs about the formal complexity of natural language. We will ignore this objection for now, since conveniently imagining that English has an infinite number of sentences can prove enlightening in understanding the properties of finite English.

A more worrisome potential flaw with this proof is that it depends on the assumption that these double relativizations of objects are strictly grammatical (even if hard to

process). The research of Karlsson (2007) suggests that, while some kinds of center-embeddings are grammatical, these double relativizations of objects are in fact ungrammatical. In any case, sentences like this get hard much faster than a billion words, and are difficult to understand after a couple nestings. We will return to this issue in Sec. 15.4.

15.3 Is NATURAL LANGUAGE CONTEXT-FREE?

The previous section argued that English (considered as a set of strings) doesn't seem like a regular language. The natural next question to ask is whether English is a context-free language. This question was first asked by Chomsky (1956), and has an interesting history; a number of well-known attempts to prove English and other languages non-context-free have been published, and all except two have been disproved after publication. One of these two correct (or at least not-yet disproved) arguments derives from the syntax of a dialect of Swiss German; the other from the morphology of Bambara, a Northwestern Mande language spoken in Mali and neighboring countries (Culy, 1985). The interested reader should see Pullum (1991, pp. 131–146) for an extremely witty history of both the incorrect and correct proofs; this section will merely summarize one of the correct proofs, the one based on Swiss German.

Both of the correct arguments, and most of the incorrect ones, make use of the fact that the following languages, and ones that have similar properties, are not context-free:

$$ \{x x\mid x\in\{a,b\}^{*}\} $$

This language consists of sentences containing two identical strings concatenated. The following related language is also not context-free:

$$ a^{n}b^{m}c^{n}d^{m} $$

The non-context-free nature of such languages can be shown using the pumping lemma for context-free languages.

CROSS-SERIAL DEPENDENCIES

The attempts to prove that the natural languages are not a subset of the context-free languages do this by showing that natural languages have a property of these $ xx $ languages called cross-serial dependencies. In a cross-serial dependency, words or larger structures are related in left-to-right order as shown in Fig. 15.5. A language that has arbitrarily long cross-serial dependencies can be mapped to the $ xx $ languages.

The successful proof, independently proposed by Huybregts (1984) and Shieber (1985) (as we might expect from the prevalence of multiple discovery in science; see page ??) shows that a dialect of Swiss German spoken in Zürich has cross-serial constraints which make certain parts of that language equivalent to the non-context-free language $ a^p b^m c^n d^m $. The intuition is that Swiss German allows a sentence to have a string of dative nouns followed by a string of accusative nouns, followed by a string of dative-taking verbs, followed by a string of accusative-taking verbs.

We will follow the version of the proof presented in Shieber (1985). First, he notes that Swiss German allows verbs and their arguments to be ordered cross-serially. Assume that all the example clauses we present below are preceded by the string “Jan säit das” (“Jan says that”):

...mer em Hans es huus halfed aastriiche

...we Hans/DAT the house/ACC helped paint.

"...we helped Hans paint the house."

Notice the cross-serial nature of the semantic dependency: both nouns precede both verbs, and em Hans (Hans) is the argument of halfed (helped) while es huus (the house) is the argument of aastriiche (paint). Furthermore, there is a cross-serial case dependency between the nouns and verbs; halfed (helped) requires the dative, and em Hans is dative, while aastriiche (paint) takes the accusative, and es huus (the house) is accusative.

Shieber points out that this case marking can occur even across triply embedded cross-serial clauses like the following:

...mer d'chind em Hans es huus haend wele laa

...we the children/ACC Hans/DAT the house/ACC have wanted to let

häife aastriiche.

help paint.

"...we have wanted to let the children help Hans paint the house."

Shieber notes that among such sentences, those with all dative NPs preceding all accusative NPs, and all dative-subcategorizing V's preceding all accusative-subcategorizing V's are acceptable.

Jan säit das mer (d’chind)^* (em Hans)^* es huus haend wele laa^* hälfe^* aastriche.

Let's call the regular expression above R. Since it's a regular expression (you see it only has concatenation and Kleene stars) it must define a regular language, and so we can intersect R with Swiss German, and if the result is context free, so is Swiss German.

But it turns out that Swiss German requires that the number of verbs requiring dative objects (hälfe) must equal the number of dative NPs (em Hans) and similarly for accusatives. Furthermore, an arbitrary number of verbs can occur in a subordinate clause of this type (subject to performance constraints). This means that the result of intersecting this regular language with Swiss German is the following language:

(15.11) L = Jan säit das mer (d’chind) $ ^n $(em Hans) $ ^m $ es huus haend wele (laa) $ ^n $ (hälfe) $ ^m $ aastriiche.

But this language is of the form $ wa^nb^m xc^nd^my $, which is not context-free! So we can conclude that Swiss German is not context free.

15.4 COMPLEXITY AND HUMAN PROCESSING

We noted in passing earlier that many of the sentences that were used to argue for the non-finite state nature of English (like the “center-embedded” sentences) are quite difficult to understand. If you are a speaker of Swiss German (or if you have a friend who is), you will notice that the long cross-serial sentences in Swiss German are also rather difficult to follow. Indeed, as Pullum and Gazdar (1982) point out,

precisely those construction-types that figure in the various proofs that English is not context-free appear to cause massive difficulty in the human processing system...

This brings us to a second use of the term complexity. In the previous section we talked about the complexity of a language. Here we turn to a question that is as much psychological as computational: the complexity of an individual sentence. Why are certain sentences hard to comprehend? Can this tell us anything about computational processes?

Many things can make a sentence hard to understand. For example we saw in Ch. 14 that a word is read more slowly if it is unpredictable; i.e., has a low N-gram probability or a low parse probability. We also saw in Ch. 14 garden-path sentences where ambiguity can cause difficulty; if there are multiple possible parses, a human reader (or listener) sometimes chooses the incorrect parse, leading to a double-take when switching back to the other parse. Other factors that affect sentence difficulty include implausible meanings and bad handwriting.

Another kind of difficulty seems to be related to human memory limitations, and it is this particular kind of complexity (often called “linguistic complexity” or “syntactic complexity”) that bears an interesting relation to the formal-language complexity from the previous section.

Consider these sentences from Gibson (1998) that cause difficulties when people try to read them (we will use the # to mean that a sentence causes extreme processing difficulty). In each case the (ii) example is significantly more complex than the (i) example:

(i) The cat likes tuna fish.

(ii) #The cat the dog the rat the goat licked bit chased likes tuna fish.

(i) The child damaged the pictures which were taken by the photographer who the professor met at the party.

(ii) #The pictures which the photographer who the professor met at the party took were damaged by the child.

(i) The fact that the employee who the manager hired stole office supplies worried the executive.

(ii) #The executive who the fact that the employee stole office supplies worried hired the manager.

The earliest work on sentences of this type noticed that they all exhibit nesting or center-embedding (Chomsky, 1957; Yngve, 1960; Chomsky and Miller, 1963; Miller and Chomsky, 1963). That is, they all contain examples where a syntactic category A is nested within another category B, and surrounded by other words (X and Y):

[B X[A]Y]

In each of the examples above, part (i) has zero or one embedding, while part (ii) has two or more embeddings. For example in (15.12ii) above, there are three reduced relative clauses embedded inside each other:

[S The cat [S' the dog [S' the rat [S' the elephant admired] bit] chased] likes tuna fish].

In (15.13ii), the relative clause who the professor met at the party is nested in between the photographer and took. The relative clause which the photographer ... took is then nested between The pictures and were damaged by the child.

#The pictures [ which the photographer [ who the professor met at the party ] took ] were damaged by the child.

The difficulty with these nested structures is not caused by ungrammaticality, since the structures that are used in the complex sentences in (15.12ii)–(15.14ii) are the same ones used in the easier sentences (15.12i)–(15.14i). The difference between the easy and complex sentences seems to relate to the number of embeddings. But there is no natural way to write a grammar that allows N embeddings but not $ N+1 $ embeddings. Rather, the complexity of these sentences seems to be a processing phenomenon; some fact about the human parsing mechanism is unable to deal with these kinds of multiple nestings, in English and in other languages (Cowper, 1976; Babyonyshev and Gibson, 1999).

The difficulty of these sentences seems to have something to do with memory limitations. Early formal grammarians suggested that this might have something to do with how the parser processed embeddings. For example Yngve (1960) suggested that the human parser is based on a limited-size stack, and that the more incomplete phrase-structure rules the parser needs to store on the stack, the more complex the sentence. Miller and Chomsky (1963) hypothesized that self-embedded structures are particularly difficult. A self-embedded structure contains a syntactic category A nested within another example of A, and surrounded by other words (x and y below); such structures might be difficult because a stack-based parser might confuse two copies of the rule on the stack.

The intuitions of these early models are important, although we no longer believe that the complexity problems have to do with an actual stack. For example, we now know that there are complexity differences between sentences that have the same number of embeddings, such as the well-known difference between subject-extracted relative clauses (15.17ii) and object-extracted relative clauses (15.17i):

(i) [s The reporter [s' who [s the senator attacked]] admitted the error].

(ii) [s The reporter [s' who [s attacked the senator]] admitted the error].

The object-extracted relative clauses are more difficult to process, as measured for example by the amount of time it takes to read them, and other factors (MacWhinney, 1977, 1982; MacWhinney and Csaba Pléh, 1988; Ford, 1983; Wanner and Maratsos, 1978; King and Just, 1991; Gibson, 1998). Indeed, Karlsson (2007) has shown in a study of seven languages that the grammaticality of center embeddings depends a lot

on the particular syntactic structure (e.g., relative clauses versus double relativization of objects) being embedded. Another problem for the old-fashioned stack-based models is the fact that discourse factors can make some doubly nested relative clauses easier to process, such as the following double nested example:

(15.18) The pictures [ that the photographer [ who I met at the party ] took ] turned out very well.

What seems to make this structure less complex is that one of the embedded NPs is the word I; pronouns like I and you seem to be easier to process, perhaps because they do not introduce a new entity to the discourse.

One human parsing model that accounts for all of this data is the Dependency Locality Theory (Gibson, 1998, 2003). The intuition of the DLT is that object relatives are difficult because they have two nouns that appear before any verb. The reader must hold on to these two nouns without knowing how they will fit into the sentences.

More specifically, the DLT proposes that the processing cost of integrating a new word w is proportional to the distance between w and the syntactic item with which w is being integrated. Distance is measured not just in words, but in how many new phrases or discourse referents have to be held in memory at the same time. Thus the memory load for a word is higher if there have been many intervening new discourse referents since the word has been predicted. Thus the DLT predicts that a sequence of NPs can be made easier to process if one of them is a pronoun that is already active in the discourse, explaining (15.18).

In summary, the complexity of these ‘center-embedded’ and other examples does seem to be related to memory, although not in as direct a link to parsing stack size as was first thought 40 years ago. Understanding the relationship between these memory factors and the statistical parsing factors mentioned in Ch. 14 is an exciting research area that is just beginning to be investigated.

15.5 SUMMARY

This chapter introduced two different ideas of complexity: the complexity of a formal language, and the complexity of a human sentence.

• Grammars can be characterized by their generative power. One grammar is of greater generative power or complexity than another if it can define a language that the other cannot define. The Chomsky hierarchy is a hierarchy of grammars based on their generative power. It includes Turing equivalent, context-sensitive, context-free, and regular grammars.

The pumping lemma can be used to prove that a given language is not regular. English is not a regular language, although the kinds of sentences that make English non-regular are exactly those that are hard for people to parse. Despite many decades of attempts to prove the contrary, English does, however, seem to be a context-free language. The syntax of Swiss-German and the morphology of Bambara, by contrast, are not context-free and seem to require mildly context-sensitive grammars.

• Certain center-embedded sentences are hard for people to parse. Many theories agree that this difficulty is somehow caused by memory limitations of the human parser.

BIBLIOGRAPHICAL AND HISTORICAL NOTES

Chomsky (1956) first asked whether finite-state automata or context-free grammars were sufficient to capture the syntax of English. His suggestion in that paper that English syntax contained “examples that are not easily explained in terms of phrase structure” was a motivation for his development of syntactic transformations.

Choksky’s proof was based on the language $\{xx^R : x \in \{a, b\}^*\}$. $x^R$ means “the reverse of $x$”, so each sentence of this language consists of a string of $as$ and $bs$ followed by the reverse or “mirror image” of the string. This language is not regular; Partee et al. (1990) shows this by intersecting it with the regular language $aa^*bba^*$. The resulting language is $a^n b^2 a^n$; it is left as an exercise for the reader (Exercise 15.3) to show that this is not regular by the pumping lemma.

Chomsky proof shows that English had mirror-like properties, relying on multiple embeddings of the following English syntactic structures, where $ S_1, S_2, \ldots, S_n $ are declarative sentences in English,

• If $ S_{1} $, then $ S_{2} $

• Either $ S_{3} $, or $ S_{4} $

• The man who said $ S_{5} $ is arriving today

See Chomsky (1956) for details.

Pullum (1991, pp. 131–146) is the definitive historical study of research on the non-context-free-ness of natural language. The early history of attempts to prove natural languages non-context-free is summarized in Pullum and Gazdar (1982). The pumping lemma was originally presented by Bar-Hillel et al. (1961), who also offer a number of important proofs about the closure and decidability properties of finite-state and context-free languages. Further details, including the pumping lemma for context-free languages (also due to Bar-Hillel et al. (1961)) can be found in a textbook in automata theory such as Hopcroft and Ullman (1979).

Yngve's idea that the difficulty of center-embedded sentences could be explained if the human parser was finite-state was taken up by Church (1980) in his master's thesis. He showed that a finite-state parser that implements this idea could also explain a number of other grammatical and psycholinguistic phenomena. While the cognitive modeling field has turned toward more sophisticated models of complexity, Church's work can be seen as the beginning of the return to finite-state models in speech and language processing that characterized the 1980s and 1990s.

There are a number of other ways of looking at complexity that we didn't have space to go into here. One is whether language processing is NP-complete. NP-complete is the name of a class of problems which are suspected to be particularly difficult to process. Barton et al. (1987) prove a number of complexity results about

the NP-completeness of natural language recognition and parsing. Among other things, they showed that

1. Maintaining lexical and agreement feature ambiguities over a potentially infinite-length sentence causes the problem of recognizing sentences in some unification-based formalisms like Lexical-Functional Grammar to be NP-complete.

2. Two-level morphological parsing (or even just mapping between lexical and surface form) is also NP-complete.

Recent work has also begun to link processing complexity with information-theoretic measures like Kolmogorov complexity (Juola, 1999).

Finally, recent work has looked at the expressive power of different kinds of probabilistic grammars, showing for example that weighted context-free grammars (in which each rule has a weight) and probabilistic context-free grammars (in which the weights of the rules for a non-terminal must sum to 1) are equally expressive (Smith and Johnson, 2007; Abney et al., 1999; Chi, 1999).

EXERCISES

15.1 Is the language $ a^nb^2a^n $ context-free?

15.2 Use the pumping lemma to show this language is not regular:

$$ L=x^{n} y^{n-1}likes~tuna~fish,x\in A,y\in B $$

15.3 Partee et al. (1990) showed that the language $ xx^R, x \in a, b^* $ is not regular, by intersecting it with the regular language $ aa^* b baa^* $. The resulting language is $ a^n b^2 a^n $. Use the pumping lemma to show that this language is not regular, completing the proof that $ xx^R, x \in a, b^* $ is not regular.

15.4 Build a context-free grammar for the language

$$ L=\{x x^{R}|x\in a,b\ast\} $$

Abney, S. P., McAllester, D. A., and Pereira, F. C. N. (1999). Relating probabilistic grammars and automata. In ACL-99.

Babyonyshev, M. and Gibson, E. (1999). The complexity of nested structures in Japanese. Language, 75(3), 423–450.

Bar-Hillel, Y., Perles, M., and Shamir, E. (1961). On formal properties of simple phrase structure grammars. Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung, 14, 143–172. Reprinted in Y. Bar-Hillel. (1964). Language and Information: Selected Essays on their Theory and Application, Addison-Wesley 1964, 116–150.

Barton, Jr., G. E., Berwick, R. C., and Ristad, E. S. (1987). Computational Complexity and Natural Language. MIT Press.

Chi, Z. (1999). Statistical Properties of Probabilistic Context-Free Grammars. Computational Linguistics, 25(1), 131–160.

Chomsky, N. (1956). Three models for the description of language. IRE Transactions on Information Theory, 2(3), 113–124.

Chomsky, N. (1957). Syntactic Structures. Mouton, The Hague.

Chomsky, N. (1959). On certain formal properties of grammars. Information and Control, 2, 137–167.

Chomsky, N. and Halle, M. (1968). The Sound Pattern of English. Harper and Row.

Chomsky, N. and Miller, G. A. (1958). Finite-state languages. Information and Control, 1, 91–112.

Chomsky, N. and Miller, G. A. (1963). Introduction to the formal analysis of natural languages. In Luce, R. D., Bush, R., and Galanter, E. (Eds.), Handbook of Mathematical Psychology, Vol. 2, pp. 269–322. Wiley.

Church, K. W. (1980). On memory limitations in natural language processing. Master's thesis, MIT. Distributed by the Indiana University Linguistics Club.

Cowper, E. A. (1976). Constraints on Sentence Complexity: A Model for Syntactic Processing. Ph.D. thesis, Brown University, Providence, RI.

Culy, C. (1985). The complexity of the vocabulary of Bambara. Linguistics and Philosophy, 8, 345–351.

Ford, M. (1983). A method for obtaining measures of local parsing complexity through sentences. Journal of Verbal Learning and Verbal Behavior, 22, 203–218.

Gibson, E. (1998). Linguistic complexity: Locality of syntactic dependencies. Cognition, 68, 1–76.

Gibson, E. (2003). Sentence comprehension, linguistic complexity in. In Nadel, L. (Ed.), Encyclopedia of Cognitive Science, pp. 1137–1141. Nature Publishing Group, New York, NY.

Hopcroft, J. E. and Ullman, J. D. (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, MA.

Huybregts, R. (1984). The weak inadequacy of context-free phrase structure grammars. In de Haan, G., Trommele, M., and Zonneveld, W. (Eds.), Van Periferie naar Kern. Foris, Dordrecht†. Cited in Pullum (1991).

Johnson, C. D. (1972). Formal Aspects of Phonological Description. Mouton, The Hague. Monographs on Linguistic Analysis No. 3.

Joshi, A. K., Vijay-Shanker, K., and Weir, D. J. (1991). The convergence of mildly context-sensitive grammatical formalisms. In Sells, P., Shieber, S., and Wasow, T. (Eds.), Foundational issues in natural language processing, pp. 31–81. MIT Press.

Joshi, A. K. (1985). Tree adjoining grammars: how much context-sensitivity is required to provide reasonable structural descriptions?. In Dowty, D. R., Karttunen, L., and Zwicky, A. (Eds.), Natural Language Parsing, pp. 206–250. Cambridge University Press.

Juola, P. (1999). Measuring linguistic complexity. Presented at the 4th Conference on Conceptual Structure, Discourse, and Language (CSDL-4), Georgia.

Karlsson, F. (2007). Constraints on multiple center-embedding of clauses. Journal of Linguistics, 43, 365–392.

King, J. and Just, M. A. (1991). Individual differences in syntactic processing: The role of working memory. Journal of Memory and Language, 30, 580–602.

Lewis, H. and Papadimitriou, C. (1988). Elements of the Theory of Computation. Prentice-Hall. Second edition.

MacWhinney, B. (1977). Starting points. Language, 53, 152–168.

MacWhinney, B. (1982). Basic syntactic processes. In Kuczaj, S. (Ed.), Language Acquisition: Volume 1, Syntax and Semantics, pp. 73–136. Lawrence Erlbaum.

MacWhinney, B. and Csaba Pléh (1988). The processing of restrictive relative clauses in Hungarian. Cognition, 29, 95–141.

Miller, G. A. and Chomsky, N. (1963). Finitary models of language users. In Luce, R. D., Bush, R. R., and Galanter, E. (Eds.), Handbook of Mathematical Psychology, Vol. II, pp. 419–491. John Wiley.

Mohri, M. and Sproat, R. (1998). On a common fallacy in computational linguistics. In Suominen, M., Arppe, A., Airola, A., Heinämäki, O., Miestamo, M., Määttä, U., Niemi, J., Pitkänen, K. K., and Sinnemäki, K. (Eds.), A Man of Measure: Festschrift in Honour of Fred Karlsson on this 60th Birthday, pp. 432–439. SKY Journal of Linguistics, Volume 19, 2006.

Partee, B. H., ter Meulen, A., and Wall, R. E. (1990). Mathematical Methods in Linguistics. Kluwer, Dordrecht.

Pollard, C. (1984). Generalized phrase structure grammars, head grammars, and natural language. Ph.D. thesis, Stanford University.

Pullum, G. K. and Gazdar, G. (1982). Natural languages and context-free languages. Linguistics and Philosophy, 4, 471–504.

Pullum, G. K. (1991). The Great Eskimo Vocabulary Hoax. University of Chicago, Chicago, IL.

Shieber, S. M. (1985). Evidence against the context-freeness of natural language. Linguistics and Philosophy, 8, 333–343.

Smith, N. A. and Johnson, M. (2007). Weighted and probabilistic context-free grammars are equally expressive. Computational Linguistics. To appear.

Stabler, E. (1997). Derivational minimalism. In Retoré, C. (Ed.), Logical Aspects of Computational Linguistics, pp. 68–95. Springer.

Steedman, M. (1996). Surface Structure and Interpretation. MIT Press. Linguistic Inquiry Monograph, 30.

Steedman, M. (2000). The Syntactic Process. The MIT Press.

Wanner, E. and Maratsos, M. (1978). An ATN approach to comprehension. In Halle, M., Bresnan, J., and Miller, G. A. (Eds.), Linguistic Theory and Psychological Reality, pp. 119–161. MIT Press.

Yngve, V. H. (1960). A model and an hypothesis for language structure. Proceedings of the American Philosophical Society, 104, 444–466.

16 FEATURES AND UNIFICATION

FRIAR FRANCIS: If either of you know any inward impediment why you should not be conjoined, charge you, on your souls, to utter it.

William Shakespeare, Much Ado About Nothing

From a reductionist perspective, the history of the natural sciences over the last few hundred years can be seen as an attempt to explain the behavior of larger structures by the combined action of smaller primitives. In biology, the properties of inheritance have been explained by the action of genes, and then again the properties of genes have been explained by the action of DNA. In physics, matter was reduced to atoms and then again to subatomic particles. The appeal of reductionism has not escaped computational linguistics. In this chapter we introduce the idea that grammatical categories like VPto, Sthat, Non3sgAux, or 3sgNP, as well as the grammatical rules like $ S \rightarrow NP $ VP that make use of them, should be thought of as objects that can have complex sets of properties associated with them. The information in these properties is represented by constraints, and so these kinds of models are often called constraint-based formalisms.

Why do we need a more fine-grained way of representing and placing constraints on grammatical categories? One problem arose in Ch. 12, where we saw that naive models of grammatical phenomena such as agreement and subcategorization can lead to overgeneration problems. For example, in order to avoid ungrammatical noun phrases such as this flights and verb phrases like disappeared a flight, we were forced to create a huge proliferation of primitive grammatical categories such as Non3sgVPto, NPmass, 3sgNP and Non3sgAux. These new categories led, in turn, to an explosion in the number of grammar rules and a corresponding loss of generality in the grammar. A constraint-based representation scheme will allow us to represent fine-grained information about number and person, agreement, subcategorization, as well as semantic categories like mass/count.

Constraint-based formalisms have other advantages that we will not cover in this chapter, such as the ability to model more complex phenomena than context-free grammars, and the ability to efficiently and conveniently compute semantics for syntactic representations.

Consider briefly how this approach might work in the case of grammatical number. As we saw in Ch. 12, noun phrases like this flight and those flights can be distinguished based on whether they are singular or plural. This distinction can be captured if we associate a property called NUMBER that can have the value singular or plural, with appropriate members of the NP category. Given this ability, we can say that this flight is a member of the NP category and, in addition, has the value singular for its NUMBER property. This same property can be used in the same way to distinguish singular and plural members of the VP category such as serves lunch and serve lunch.

Of course, simply associating these properties with various words and phrases does not solve any of our overgeneration problems. To make these properties useful, we need the ability to perform simple operations, such as equality tests, on them. By pairing such tests with our core grammar rules, we can add various constraints to help ensure that only grammatical strings are generated by the grammar. For example, we might want to ask whether or not a given noun phrase and verb phrase have the same values for their respective number properties. Such a test is illustrated by the following kind of rule.

$$ S\to NP VP $$

Only if the number of the NP is equal to the number of the VP.

The remainder of this chapter provides the details of one computational implementation of a constraint-based formalism, based on feature structures and unification. The next section describes feature structures, the representation used to capture the kind of grammatical properties we have in mind. Section 16.2 then introduces the unification operator that is used to implement basic operations over feature structures. Section 16.3 then covers the integration of these structures into a grammatical formalism. Section 16.4 then introduces the unification algorithm and its required data structures. Next, Section 16.5 describes how feature structures and the unification operator can be integrated into a parser. Finally, Section 16.6 discusses the most significant extension to this constraint-based formalism, the use of types and inheritance, as well as other extensions.

16.1 FEATURE STRUCTURES

One of the simplest ways to encode the kind of properties that we have in mind is through the use of feature structures. These are simply sets of feature-value pairs, where features are unanalyzable atomic symbols drawn from some finite set, and values are either atomic symbols or feature structures themselves. Such feature structures are traditionally illustrated with the following kind of matrix-like diagram, called an attribute-value matrix or AVM:

$$ \begin{bmatrix}\text{FEATURE}_{1}&\text{value}_{1}\\ \text{FEATURE}_{2}&\text{value}_{2}\\ \vdots&\\ \text{FEATURE}_{n}&\text{value}_{n}\end{bmatrix} $$

To make this concrete, consider the number property discussed above. To capture this property, we will use the symbol NUMBER to designate this grammatical attribute, and the symbols sg and pl (introduced in Ch. 3) to designate the possible values it can take on in English. A simple feature structure consisting of this single feature would then be illustrated as follows:

$$ \left[\begin{array}{cc}NUMBER&sg\end{array}\right] $$

Adding an additional feature-value pair to capture the grammatical notion of person leads to the following feature structure:

$$ \begin{bmatrix}\text{NUMBER}&sg\\ \text{PERSON}&3rd\end{bmatrix} $$

Next we can encode the grammatical category of the constituent that this structure corresponds to through the use of the CAT feature. For example, we can indicate that these features are associated with a noun phrase by using the following structure:

$$ \begin{bmatrix}\text{CAT}&N P\\ \text{NUMBER}&s g\\ \text{PERSON}&3r d\end{bmatrix} $$

This structure can be used to represent the 3sgNP category introduced in Ch. 12 to capture a restricted subcategory of noun phrases. The corresponding plural version of this structure would be captured as follows:

$$ \begin{bmatrix}CAT&NP\\ NUMBER&pl\\ PERSON&3rd\end{bmatrix} $$

Note that the values of the CAT and PERSON features remain the same for these last two structures. This illustrates how the use of feature structures allows us to both preserve the core set of grammatical categories and draw distinctions among members of a single category.

As mentioned earlier, features are not limited to atomic symbols as their values; they can also have other feature structures as their values. This is particularly useful when we wish to bundle a set of feature-value pairs together for similar treatment. As an example of this, consider that the NUMBER and PERSON features are often lumped together since grammatical subjects must agree with their predicates in both their number and person properties. This lumping together can be captured by introducing an AGREEMENT feature that takes a feature structure consisting of the NUMBER and PERSON feature-value pairs as its value. Introducing this feature into our third person singular noun phrase yields the following kind of structure.

$$ \begin{bmatrix}CAT&NP\\ AGREEMENT&\begin{bmatrix}NUMBER&sg\\ PERSON&3rd\end{bmatrix}\end{bmatrix} $$

Given this kind of arrangement, we can test for the equality of the values for both the NUMBER and PERSON features of two constituents by testing for the equality of their AGREEMENT features.

This ability to use feature structures as values leads fairly directly to the notion of a feature path. A feature path is nothing more than a sequence of features through a feature structure leading to a particular value. For example, in the last feature structure, we can say that the $ \langle\text{AGREEMENT NUMBER}\rangle $ path leads to the value sg, while the $ \langle\text{AGREEMENT PERSON}\rangle $ path leads to the value 3rd. This notion of a path leads naturally to an alternative graphical way of illustrating feature structures, shown in Figure 16.1, which as we will see in Section 16.4 is suggestive of how they will be implemented. In these diagrams, feature structures are depicted as directed graphs where features appear as labeled edges and values as nodes.

Although this notion of paths will prove useful in a number of settings, we introduce it here to help explain an additional important kind of feature structure: those that contain features that actually share some feature structure as a value. Such feature structures will be referred to as reentrant structures. What we have in mind here is not the simple idea that two features might have equal values, but rather that they share precisely the same feature structure (or node in the graph). These two cases can be distinguished clearly if we think in terms of paths through a graph. In the case of simple equality, two paths lead to distinct nodes in the graph that anchor identical, but distinct structures. In the case of a reentrant structure, two feature paths actually lead to the same node in the structure.

Figure 16.2 illustrates a simple example of reentrancy. In this structure, the $ \langle HEAD\ SUBJECT\ AGREEMENT\rangle $ path and the $ \langle HEAD\ AGREEMENT\rangle $ path lead to the same location. Shared structures like this will be denoted in our AVM diagrams by adding numerical indexes that signal the values to be shared. The AVM version of the feature structure from Figure 16.2 would be denoted as follows, using the notation of the PATR-II system (Shieber, 1986), based on Kay (1979):

As we will see, these simple structures give us the ability to express linguistic generalizations in surprisingly compact and elegant ways.

16.2 UNIFICATION OF FEATURE STRUCTURES

As noted earlier, feature structures would be of little use without our being able to perform reasonably efficient and powerful operations on them. As we will show, the two principal operations we need to perform are merging the information content of two structures and rejecting the merger of structures that are incompatible. Fortunately, a single computational technique, called unification, suffices for both of these purposes. The bulk of this section will illustrate through a series of examples how unification instantiated these notions of merger and compatibility.

Discussion of the unification algorithm and its implementation will be deferred to Section 16.4.

We begin with the following simple application of the unification operator.

$$ \left[\begin{matrix}{\mathtt{N U M B E R}}&{s g}\\ \end{matrix}\right]\sqcup\left[\begin{matrix}{\mathtt{N U M B E R}}&{s g}\\ \end{matrix}\right]=\left[\begin{matrix}{\mathtt{N U M B E R}}&{s g}\\ \end{matrix}\right] $$

As this equation illustrates, unification is a binary operation (represented here as ⊿) that accepts two feature structures as arguments and returns a feature structure when it succeeds. In this example, unification is being used to perform a simple equality check. The unification succeeds because the corresponding NUMBER features in each structure agree as to their values. In this case, since the original structures are identical, the output is the same as the input. The following similar kind of check fails since the NUMBER features in the two structures have incompatible values.

$$ \left[\begin{matrix}{\operatorname{N U M B E R}}&{s g}\\ \end{matrix}\right]\sqcup\left[\begin{matrix}{\operatorname{N U M B E R}}&{p l}\\ \end{matrix}\right]{F a i l s!} $$

This next unification illustrates an important aspect of the notion of compatibility in unification.

NUMBER

$$ s g]\sqcup\left[\begin{matrix}{\operatorname{N U M B E R}}&{[]}\\ \end{matrix}\right]=\left[\begin{matrix}{\operatorname{N U M B E R}}&{s g}\\ \end{matrix}\right] $$

In this situation, these features structures are taken to be compatible, and are hence capable of being merged, despite the fact that the given values for the respective NUMBER features are different. The [] value in the second structure indicates that the value has been left unspecified. A feature with such a [] value can be successfully matched to any value in a corresponding feature in another structure.

Therefore, in this case, the value $ s_g $ from the first structure can match the [] value from the second, and as is indicated by the output shown, the result of this type of unification is a structure with the value provided by the more specific, non-null, value.

The next example illustrates another of the merger aspects of unification.

$$ \begin{bmatrix}\text{NUMBER}&sg\end{bmatrix}\sqcup\begin{bmatrix}\text{PERSON}&3rd\end{bmatrix}=\begin{bmatrix}\text{NUMBER}&sg\\ \text{PERSON}&3rd\end{bmatrix} $$

Here the result of the unification is a merger of the original two structures into one larger structure. This larger structure contains the union of all the information stored in each of the original structures. Although this is a simple example, it is important to understand why these structures are judged to be compatible: they are compatible because they contain no features that are explicitly incompatible. The fact that they each contain a feature-value pair that the other does not is not a reason for the unification to fail.

We will now consider a series of cases involving the unification of somewhat more complex reentrant structures. The following example illustrates an equality check complicated by the presence of a reentrant structure in the first argument.

The important elements in this example are the SUBJECT features in the two input structures. The unification of these features succeeds because the values found in the first argument by following the ① numerical index, match those that are directly present in the second argument. Note that, by itself, the value of the AGREEMENT feature in the first argument would have no bearing on the success of unification since the second argument lacks an AGREEMENT feature at the top level. It only becomes relevant because the value of the AGREEMENT feature is shared with the SUBJECT feature.

The following example illustrates the copying capabilities of unification.

Here the value found via the second argument's $ \langle SUBJECT\ AGREEMENT\rangle $ path is copied over to the corresponding place in the first argument. In addition, the AGREEMENT feature of the first argument receives a value as a side-effect of the index linking it to the value at the end of the $ \langle SUBJECT\ AGREEMENT\rangle $ path.

The next example demonstrates the important difference between features that actually share values versus those that merely have identical looking values.

The values at the end of the $ \langle SUBJECT\ AGREEMENT\rangle $ path and the $ \langle AGREEMENT\rangle $ path are the same, but not shared, in the first argument. The unification of the SUBJECT features of the two arguments adds the PERSON information from the second argument to the result. However, since there is no index linking the AGREEMENT feature to the $ \langle SUBJECT\ AGREEMENT\rangle $ path, this information is not added to the value of the AGREEMENT feature.

Finally, consider the following example of a failure to unify.

Proceeding through the features in order, we first find that the AGREEMENT features in these examples successfully match. However, when we move on to the SUBJECT features, we find that the values found at the respective $ \langle $ SUBJECT AGREEMENT NUMBER $ \rangle $ paths differ, causing a unification failure.

Feature structures are a way of representing partial information about some linguistic object or placing informational constraints on what the object can be. Unification can be seen as a way of merging the information in each feature structure, or describing objects which satisfy both sets of constraints. Intuitively, unifying two feature structures produces a new feature structure which is more specific (has more information) than, or is identical to, either of the input feature structures. We say that a less specific (more abstract) feature structure \textit{subsumes} an equally or more specific one. Subsumption is represented by the operator $ \sqsubseteq $. A feature structure $ F $ subsumes a feature structure $ G $ ( $ F \sqsubseteq G $) if and only if:

1. For every feature $x$ in $F$, $F(x) \subseteq G(x)$ (where $F(x)$ means “the value of the feature $x$ of feature structure $F$”).

2. For all paths $p$ and $q$ in $F$ such that $F(p) = F(q)$, it is also the case that $G(p) = G(q)$.

For example, consider these feature structures:

NUMBER sg

PERSON 3

$$ \begin{bmatrix}NUMBER&sg\\PERSON&3\end{bmatrix} $$

(16.6)

(16.7)

The following subsumption relations hold among them:

$$ 16.3\sqsubseteq16.5 $$

$$ 16.4\sqsubseteq16.5 $$

$$ 16.6\sqsubseteq16.7 $$

Subsumption is a partial ordering; there are pairs of feature structures that neither subsume nor are subsumed by each other:

$$ 16.3\not\sqsubseteq16.4 $$

$$ 16.4\not\sqsubseteq16.3 $$

Since every feature structure is subsumed by the empty structure [], the relation among feature structures can be defined as a semilattice. Unification can be defined in terms of the subsumption semilattice. Given two feature structures $ F $ and $ G $, $ F \sqcup G $ is defined as the most general feature structure $ H $ such that $ F \sqsubseteq H $ and $ G \sqsubseteq H $. Since the information ordering defined by subsumption is a semilattice, the unification operation is monotonic (Pereira and Shieber, 1984; Rounds and Kasper, 1986; Moshier, 1988). This means that if some description is true of a feature structure, unifying it with another feature structure results in a feature structure that still satisfies the original description. The unification operation is therefore associative; given a finite set of feature structures to unify, we can check them in any order and get the same result.

To summarize, unification is a way of implementing the integration of knowledge from different constraints. Given two compatible feature structures as input, it produces the most general feature structure which nonetheless contains all the information in the inputs. Given two incompatible feature structures, it fails.

16.3 FEATURE STRUCTURES IN THE GRAMMAR

Our primary purpose in introducing feature structures and unification has been to provide a way to elegantly express syntactic constraints that would be difficult to express using the mechanisms of context-free grammars alone. Our next step, therefore, is to specify a way to integrate feature structures and unification operations into the specification of a grammar. This can be accomplished by augmenting

the rules of ordinary context-free grammars with attachments that specify feature structures for the constituents of the rules, along with appropriate unification operations that express constraints on those constituents. From a grammatical point of view, these attachments will be used to accomplish the following goals:

• to associate complex feature structures with both lexical items and instances of grammatical categories

• to guide the composition of feature structures for larger grammatical constituents based on the feature structures of their component parts

• to enforce compatibility constraints between specified parts of grammatical constructions

We will use the following notation to denote the grammar augmentations that will allow us to accomplish all of these goals, based on the PATR-II system described in Shieber (1986):

$$ \beta_{0}\to\beta_{1}\cdots\beta_{n} $$

$$ \{set~of~constraints\} $$

The specified constraints have one of the following forms.

$$ \langle\beta_{i}{~f e a t u r e~p a t h}\rangle={A t o m i c~v a l u e} $$

$$ \langle\beta_{i}{~f e a t u r e~p a t h}\rangle\;=\;\langle\beta_{j}{~f e a t u r e~p a t h}\rangle $$

The notation $ \langle\beta_{i}\text{ feature path}\rangle $ denotes a feature path through the feature structure associated with the $ \beta_{i} $ component of the context-free part of the rule. The first style of constraint specifies that the value found at the end of the given path must unify with the specified atomic value. The second form specifies that the values found at the end of the two given paths must be unifiable.

To illustrate the use of these constraints, let us return to the informal solution to the number agreement problem proposed at the beginning of this chapter.

$$ S\rightarrow NP VP $$

Only if the number of the NP is equal to the number of the VP.

Using the new notation, this rule can now be expressed as follows.

$$ S\to NP VP $$

$$ \left\langle N P\ \mathrm{N U M B E R}\right\rangle=\left\langle V P\ \mathrm{N U M B E R}\right\rangle $$

Note that in cases where there are two or more constituents of the same syntactic category in a rule, we will subscript the constituents to keep them straight, as in $ VP \rightarrow VNP_{1} NP_{2} $.

Taking a step back from the notation, it is important to note that in this approach the simple generative nature of context-free rules has been fundamentally changed by this augmentation. Ordinary context-free rules are based on the simple

notion of concatenation; an NP followed by a VP is an S, or generatively, to produce an S all we need to do is concatenate an NP to a VP. In the new scheme, this concatenation must be accompanied by a successful unification operation. This leads naturally to questions about the computational complexity of the unification operation and its effect on the generative power of this new grammar. These issues will be discussed in Ch. 15.

To review, there are two fundamental components to this approach.

• The elements of context-free grammar rules will have feature-based constraints associated with them. This reflects a shift from atomic grammatical categories to more complex categories with properties.

The constraints associated with individual rules can make reference to the feature structures associated with the parts of the rule to which they are attached.

The following sections present applications of unification constraints to four interesting linguistic phenomena: agreement, grammatical heads, subcategorization, and long-distance dependencies.