Paper: Finite-State Approximation Of Phrase Structure Grammars

ACL ID P91-1032
Title Finite-State Approximation Of Phrase Structure Grammars
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 1991

Phrase-structure grammars are an effective rep- resentation for important syntactic and semantic aspects of natural languages, but are computa- tionally too demanding for use as language mod- els in real-time speech recognition. An algorithm is described that computes finite-state approxi- mations for context-free grammars and equivalent augmented phrase-structure grammar formalisms. The approximation is exact for certain context- free grammars generating regular languages, in- cluding all left-linear and right-linear context-free grammars. The algorithm has been used to con- struct finite-state language models for limited- domain speech recognition tasks. 1 Motivation Grammars for spoken language systems are sub- ject to the conflicting requirements of language modeling for recognition an...