Abstract
This paper investigates the computational constraints of human natural language processing, arguing that human parsing can be modeled by a Finite State Machine (FSM) rather than a computationally more powerful Turing Machine. By implementing a parser called YAP (Yet Another Parser) that utilizes a bounded stack and a novel "A-over-A" closure strategy, the research demonstrates that human processing failures—such as the inability to parse deep center-embedding—are not bugs, but predictable consequences of finite memory limits. This model provides a unified account of how humans efficiently process unbounded right-recursive structures while remaining susceptible to garden-path effects and memory overflows in specific linguistic configurations.
Introduction
In the late 1970s and early 1980s, the prevailing view in computational linguistics was that natural language was sufficiently complex to require the power of a Turing Machine, implying a need for essentially infinite memory. However, Kenneth Church identifies a fundamental contradiction in this assumption: while human language "competence" (the idealized rules of grammar) might allow for infinite recursion, human "performance" (actual processing) is remarkably limited. Humans consistently fail to parse certain technically grammatical sentences, most notably those involving deep center-embedding (e.g., "The rat the cat the dog chased bit ate the cheese").
Church addresses this gap by proposing that the human parser is not a Turing Machine, but a Finite State Machine. This "Finite State Hypothesis" suggests that the bottlenecks in human short-term memory are a defining feature of our linguistic architecture. By restricting the computational power of the parser, we can more accurately model the specific strengths and weaknesses of human language processing.
The YAP Parser and Memory Constraints
To test the Finite State Hypothesis, Church developed YAP (Yet Another Parser). Unlike standard parsers of the era that allowed for an infinitely growing stack, YAP operates with a strictly bounded stack to simulate the limitations of human short-term memory. A critical challenge in such a system is "closure" or garbage collection: the parser must decide when a phrase is complete so it can be removed from the stack to make room for new input.
Church evaluates two existing closure strategies:
- Kimball’s Early Closure: This strategy is often too aggressive, discarding information prematurely and preventing the parser from making necessary later attachments.
- Frazier’s Late Closure: This strategy is too conservative, keeping phrases on the stack as long as possible. While accurate, it quickly leads to stack overflows even on simple, long sentences that humans find easy to process.
The A-over-A Early Closure Principle
Church introduces a novel compromise known as the A-over-A Early Closure Principle. Under this heuristic, the parser closes a phrase only when two phrases of the same category (e.g., two Noun Phrases or two Clauses) are currently held on the stack and specific conditions are met.
This principle acts as a form of "tail-recursion" optimization for natural language. It allows the parser to process infinitely long right-branching sentences—which humans handle with ease—using only a small, fixed amount of memory. Conversely, it naturally fails on deep center-embedding because those structures require the stack to hold multiple nested instances of the same category without the opportunity for closure, leading to an inevitable overflow. This effectively mirrors the human experience of "losing the thread" in complex nested sentences.
Key Insights and Determinism
A central theme of the paper is that computational complexity is a feature, not a bug. By imposing hardware-level limitations (like a finite stack), the task of parsing actually becomes more tractable. Church integrates this with Marcus’s "Determinism Hypothesis," which posits that the human parser does not backtrack. When combined with memory limits, this provides a robust explanation for "Garden Path" sentences (e.g., "The horse raced past the barn fell"). In these cases, the parser makes a definitive choice to close a phrase or attach a word based on its limited window, and when that choice proves wrong, it has no mechanism to recover, exactly as humans experience.
Furthermore, Church distinguishes between "movement" and "embedding." Movement phenomena (like Wh-questions) typically have a bounded memory cost, explaining why they are easily processed. Center-embedding has an unbounded cost, explaining the sharp drop-off in human performance as nesting depth increases.
Conclusion and Limitations
The YAP parser successfully demonstrates that a Finite State Machine is a sufficient model for human linguistic performance. It qualitatively matches human behavior by successfully parsing acceptable sentences while failing on unacceptable, though grammatical, structures.
However, Church acknowledges that the A-over-A principle is somewhat ad hoc and requires further refinement to explain the full spectrum of human attachment preferences. The model also does not precisely define the exact physical limit of the human stack (e.g., whether it is three or four levels), only that a finite limit must exist. Future work is required to bridge the gap between this computational model and empirical psycholinguistic data to fully solve the "closure puzzle."
Summary updated