Chomsky's Syntactic Structures (1957) › The Limits of Finite-State Models

The problem facing linguists in the 1950s was one of descriptive adequacy. How could you precisely characterize what made some strings of words grammatical sentences while others were just word salad? The dominant approach borrowed from information theory and early computer science: finite-state models. These mathematical systems, which would later become fundamental to computer science as finite automata, seemed perfectly suited to describing language.

A finite-state model processes input sequentially, word by word, transitioning between a finite set of internal states. At each step, the current state and the next word determine which state to transition to next. If you reach an accepting state after processing all the words, you've recognized a grammatical sentence. The appeal was obvious. These models were mathematically precise, computationally tractable, and already being used successfully in early natural language processing applications. Claude Shannon had used similar probabilistic models to generate surprisingly realistic-looking English text. Engineers at Bell Labs were using them for speech recognition. The path forward seemed clear.

But Chomsky saw something others had missed. English contains sentence structures that finite-state models simply cannot capture, no matter how many states they have. Consider sentences with nested dependencies: "If the man whom you saw yesterday comes today, I will leave." The "if" at the beginning requires a matching "then" or main clause somewhere later. The relative clause "whom you saw yesterday" is embedded in the middle, interrupting the dependency between "man" and "comes." These nested, hierarchical structures appear everywhere in natural language. We can embed clauses within clauses within clauses, creating dependencies that span arbitrary distances.

A finite-state model processes language linearly, maintaining only information about its current state. It has no memory of arbitrary depth, no way to count nested structures or track multiple long-distance dependencies simultaneously. Chomsky proved this wasn't just a practical limitation that could be overcome with more states.it was a fundamental mathematical impossibility. Languages with nested dependencies, like English, required a more powerful formal system. This proof was devastating. It meant the entire finite-state approach to linguistics was built on an inadequate foundation. You couldn't describe natural language grammar with these tools, no matter how clever you were or how many states you used.