Reversible Automata and Induction of the English Auxiliary System

Robert C. Berwick, Samuel F. Pilato

Abstract

In the study of language acquisition, a central paradox exists: how do children induce complex grammatical structures from limited data in a computationally feasible timeframe? This paper, originally published by the MIT AI Lab in 1984, investigates this question by applying Dana Angluin’s theory of $k$-reversible languages to the English auxiliary verb system. By modeling the auxiliary system as a finite-state automaton, Berwick and Pilato demonstrate that specific mathematical constraints—specifically 1-reversibility—allow for the efficient induction of grammar from a subset of possible sentences, providing a formal mechanism for language learning that avoids the pitfalls of exponential search spaces.

Introduction

In the late 1960s and 70s, formal learning theory, most notably the work of E. Mark Gold, suggested that the induction of a grammar from positive examples alone was "computationally intractable." These findings implied that a learner would require an exponential amount of time or an infinite amount of data to correctly identify a language's structure. This created a significant tension between mathematical theory and empirical observation: if general induction is so difficult, how do human children master their native tongue so rapidly and effortlessly?

Linguists have traditionally resolved this paradox by positing that human language is governed by highly specific, innate constraints—a "Universal Grammar." Berwick and Pilato explore a middle ground, investigating whether more general, mathematically defined constraints on automata (state machines) could explain the efficiency of language acquisition without requiring a massive inventory of innate linguistic knowledge. They focus their analysis on the English auxiliary verb system, a complex but finite subsystem of English grammar.

Theoretical Framework: $k$-Reversible Languages

The authors utilize Dana Angluin’s (1982) theory of $k$-reversible languages. A language is considered $k$-reversible if its structure follows a consistency rule based on local context. Specifically, if two different prefixes end in the same $k$ words and share at least one "tail" (the remainder of the sentence), then they must share all possible tails.

  • 0-Reversible: This is the most aggressive form of generalization. If "Mary" and "John" both precede the phrase "bakes cakes," a 0-reversible learner assumes that anything Mary can do, John can also do. This often leads to massive overgeneralization.
  • 1-Reversible: This is a more conservative approach. It requires the last word of the prefix to match before the learner generalizes. For example, the learner looks at the specific word preceding a transition to decide if states should be merged.

In practice, the inference algorithm starts by constructing a "prefix-tree" automaton representing all observed sentences. It then systematically collapses or "merges" states that satisfy the $k$-reversibility criteria until the smallest possible $k$-reversible automaton is formed.

Methodology and Dataset

The study employed a specialized corpus consisting of 92 variants of a single English declarative statement in the third person singular. This corpus was designed to cover the full range of legal permutations in the English auxiliary system, including:

  • Tense, Aspect, and Voice: Ranging from simple active forms ("Judy gives bread") to complex passive modals ("Judy would have been given bread").
  • Modals and Do-Support: The inclusion of nine different modal verbs and the specific rules governing the auxiliary "do."
  • Raw Surface Strings: Crucially, the data consisted of raw words with no pre-assigned syntactic categories like "Verb" or "Noun," forcing the algorithm to discover patterns from the strings themselves.

The algorithm was implemented in MAC-LISP, and the researchers tested how many examples were required to reconstruct the full 92-sentence system under different $k$ constraints.

Key Insights and Results

1. The "Sweet Spot" of 1-Reversibility

The researchers found that the English auxiliary system is not 0-reversible. When the learner assumed $k=0$, it overgeneralized wildly, creating illegal word sequences and infinite loops. However, at $k=1$, the system became perfectly learnable. The learner was able to induce the full 92-sentence system from a "cover" of only 48 examples (approximately 52% of the total corpus). This demonstrates that 1-reversibility provides the necessary "inferential power" to predict unseen, grammatically correct sentences based on a limited sample.

2. The Cost of Conservatism

As the value of $k$ increases, the learner becomes more conservative. At $k=3$, the algorithm’s ability to generalize vanished; it essentially became a "tape recorder," capable only of repeating the sentences it had already seen. This suggests that human language acquisition may rely on a specific level of context-sensitivity that balances generalization with precision.

3. Psychological Plausibility

Interestingly, the errors made by the 0-reversible learner—such as incorrectly combining "do" with other modals—mirror certain developmental mistakes observed in children. This suggests that the mathematical constraints of $k$-reversibility may have real-world parallels in human cognitive development.

4. Computational Efficiency

Because Angluin’s algorithm runs in polynomial time, the learning process is computationally feasible. This provides a robust counter-argument to the notion that general induction is inherently too slow for language acquisition, provided the language belongs to a restricted class like the $k$-reversible regular languages.

Limitations and Future Directions

While the results are promising, the authors acknowledge several limitations. The English auxiliary system is a "regular" language, meaning it can be mapped by a finite automaton. However, much of human language is context-free or even more complex. While the authors suggest that $k$-reversibility could be extended to context-free rewrite rules, that extension was not implemented in this study.

Furthermore, the model operates on raw surface forms. A more robust model would likely need to incorporate abstract categories (like "Modal" or "Verb") to handle the diversity of a real-world vocabulary. Finally, the study assumes a "clean" corpus of positive examples, leaving the questions of noisy data and word frequency for future research.

Conclusion

Berwick and Pilato’s work demonstrates that the apparent impossibility of language induction can be overcome by assuming relatively simple mathematical constraints. By showing that the English auxiliary system is 1-reversible, they provide a bridge between formal learning theory and linguistic practice, suggesting that the efficiency of human language learning may stem from the underlying mathematical structure of the grammar itself.

Summary updated

BibTeX
@inproceedings{berwick1985reversible,
  author = {Robert C. Berwick and Samuel F. Pilato},
  title = {{Reversible Automata and Induction of the English Auxiliary System}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1985},
}
Figure