Approximating Context-Free Grammars with a Finite-State Calculus

Preprint

12 November 1997

preprint
Published by arXiv in arXiv

https://doi.org/10.48550/arXiv.cmp-lg/9711002

Abstract

Although adequate models of human language for syntactic analysis and semantic interpretation are of at least context-free complexity, for applications such as speech processing in which speed is important finite-state models are often preferred. These requirements may be reconciled by using the more complex grammar to automatically derive a finite-state approximation which can then be used as a filter to guide speech recognition or to reject many hypotheses at an early stage of processing. A method is presented here for calculating such finite-state approximations from context-free grammars. It is essentially different from the algorithm introduced by Pereira and Wright (1991; 1996), is faster in some cases, and has the advantage of being open-ended and adaptable.

Keywords

All Related Versions

Version 1, 1997-11-12, ArXiv

This publication has 0 references indexed in Scilit: