Finite-State Approximation of Phrase Structure Grammars

Fernando C. N. Pereira, Rebecca N. WrightACL 1991 · DOI

Introduction

In computational linguistics, a persistent tension exists between the needs of real-time speech recognition and deep semantic interpretation. Speech recognizers require the speed and efficiency of Finite-State Automata (FSA), yet human language is characterized by recursive structures and nested dependencies that FSAs cannot easily model. Conversely, Augmented Phrase-Structure Grammars (APSG) offer the necessary expressivity but are often too computationally expensive for the initial "front-end" search in a speech system. This paper presents an algorithm to bridge this gap by automatically deriving a sound finite-state approximation from a complex APSG.

Methodology: From LR(0) to FSA

The proposed method centers on the LR(0) characteristic machine, the finite-state control mechanism used in standard compilers to manage a stack during parsing. The conversion process involves several key steps:

Flattening and Unfolding

The core innovation is "flattening" the shift-reduce recognizer into an FSA. In a standard parser, "reduce" moves involve popping items off a stack. The authors transform these moves into simple $\epsilon$-transitions (empty jumps) between states.

LR(0) characteristic machine for a sample grammar.

However, simple flattening can be overly "lossy," creating an FSA that accepts many invalid strings. To mitigate this, the algorithm "unfolds" the machine's states by creating multiple copies of a state based on the stack context used to reach it. This preserves just enough context to maintain a "tight" approximation.

The corresponding flattened finite-state automaton with epsilon-transitions.

Loop Collapsing

To ensure the resulting state space remains finite despite potentially infinite stack depths, the authors employ a "loop collapsing" equivalence relation. By identifying repeating stack segments (similar to the logic of the pumping lemma), the algorithm "forgets" the specific number of repetitions, effectively bounding the state space.

Soundness and Exactness

The resulting FSA is guaranteed to be sound, meaning it will accept every string that the original grammar would accept. Furthermore, the method is exact for left-linear and right-linear grammar components. This ensures that if a complex grammar contains sections that are fundamentally regular, the approximation process will not introduce any loss of precision in those areas.

Evaluation and Results

The algorithm was tested on a small English fragment consisting of 78 nonterminals and 157 rules, covering noun phrases, verb subcategorization, and person/number agreement. The process successfully transformed this grammar into a minimized DFA with only 16 states and 97 transitions.

The computational efficiency is notable: the entire pipeline—from CFG expansion to approximation, determinization, and minimization—took only 4.91 seconds on a Sun SparcStation 1. This demonstrates the feasibility of using such approximations for real-time speech tasks that were previously too demanding for full APSG parsing.

Limitations and Conclusion

While powerful, the algorithm faces challenges in worst-case scenarios, where state unfolding can lead to an exponential explosion in the number of states. Additionally, the current handling of right-recursive rules is less efficient than desired. Future research may explore "degrees" of approximation, perhaps incorporating probabilistic weights to better quantify the precision lost during the conversion process. Nonetheless, this work provides a robust framework for leveraging linguistically rich grammars within the performance constraints of modern speech recognition systems.

Summary updated

BibTeX
@inproceedings{pereira1991finite,
  author = {Fernando C. N. Pereira and Rebecca N. Wright},
  title = {{Finite-State Approximation of Phrase Structure Grammars}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {1991},
  doi = {10.3115/981344.981376},
}
Figure