Abstract FINITE-STATE APPROXIMATION OF PHRASE STRUCTURE GRAMMARS

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.