Paper: Approximating Context-Free Grammars With A Finite-State Calculus

ACL ID P97-1058
Title Approximating Context-Free Grammars With A Finite-State Calculus
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 1997

Although adequate models of human lan- guage for syntactic analysis and seman- tic interpretation are of at least context- free complexity, for applications such as speech processing in which speed is impor- tant finite-state models are often preferred. These requirements may be reconciled by using the more complex grammar to auto- matically derive a finite-state approxima- tion 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 calculat- ing such finite-state approximations from context-free grammars. It is essentially dif- ferent from the algorithm introduced by Pereira and Wright (1991; 1996), is faster in some cases, and has the advantage of be- ing open-ended and adaptable. 1 Finit...