Introduction
In his seminal 1983 paper, Geoffrey K. Pullum challenged the prevailing linguistic orthodoxy of the era. While the field was gravitating toward increasingly complex transformational grammars, Pullum argued for a radical simplification: that Context-Free Grammars (CFGs) are not only sufficient for natural language but might actually be more powerful than necessary. He proposed that human languages occupy a highly restricted, computationally efficient niche within the context-free domain, characterized by specific ordering properties and linear-time recognition.
Challenging the Status Quo
By the early 1980s, the consensus—largely driven by the influence of Noam Chomsky—was that Context-Free Phrase Structure Grammars (CF-PSGs) lacked the "expressive power" to describe the complexities of human language. Critics argued that phenomena such as crossing dependencies or free word order necessitated more powerful formalisms. Pullum re-evaluated these claims across three critical dimensions:
- Weak Generative Capacity: Whether CFGs can generate the exact set of strings found in human languages.
- Strong Generative Capacity: Whether CFGs can assign the correct structural descriptions (trees) to those strings.
- Computational Complexity: Whether CFGs can be parsed quickly enough to model real-time human language processing.
Theoretical Framework: ECPO and Profligacy
Pullum utilized formal language theory and complexity analysis to introduce several key concepts that redefine how we view linguistic structure:
- The ECPO Property: He advocated for the Exhaustive Constant Partial Ordering property. This framework separates "Immediate Dominance" (which elements belong in a phrase) from "Linear Precedence" (the order in which they appear). This separation allows for a more elegant description of word-order variations without increasing formal power.
- The Profligacy Conjecture: Pullum defined a "profligate" language as one where any grammar generating it must have a nonterminal vocabulary (syntactic categories) strictly larger than its terminal vocabulary (words). He conjectured that human languages are never profligate, suggesting that our theories should favor a high word-to-category ratio.
- Automata Theory and Efficiency: Using the 2-way Deterministic Pushdown Automaton (2DPDA), Pullum demonstrated that certain "scrambled" languages, previously thought to be computationally expensive, can actually be recognized in linear time.
Key Insights
The "Dutch Problem" Reconsidered
Critics often cited Dutch "crossing dependencies" (e.g., Jan saw Pier teach Marie to swim) as definitive proof that natural language is non-context-free. Pullum argued that this was a category error: while the meaning involves crossing dependencies, the syntax can still be modeled by a "flat" context-free structure. He maintained that the mapping to semantics should not be confused with the formal complexity of the string generation itself.
Scrambling and Linear Time
A common intuition in the 1980s was that "free word order" languages would be a nightmare for parsers. Pullum debunked this by providing a formal proof that a "Bach language" (a scrambled version of $a^n b^n c^n$) can be recognized in linear time ($O(n)$). This proved that word-order freedom does not necessitate high computational costs or non-context-free power.
Aiming for Human-Like Speed
While standard CFG parsing is $O(n^3)$, Pullum argued that a truly restrictive theory of human language should guarantee linear-time recognition. This matches the apparent speed of human comprehension and suggests that the "human subset" of context-free languages is much smaller and more efficient than the general class.
Conclusion and Future Directions
Pullum’s work shifted the research goalpost from "finding more power" to "finding the right restrictions." He suggested that human languages are a proper subset of ECPO CF-PSGs that are nonprofligate and linear-time recognizable.
While he left open questions regarding the decidability of profligacy and the formalization of the semantic gap in "flat" structures, the paper remains a call to action. It challenges linguists to define the exact boundaries of the computationally efficient subset of languages that humans actually use—a task that continues to drive the field of computational linguistics today.
Summary updated