Approximating Context-Free Grammars with a Finite-State Calculus
<|reference_start|>Approximating Context-Free Grammars with a Finite-State Calculus: 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.<|reference_end|>
@article{grimley-evans1997approximating,
    title={Approximating Context-Free Grammars with a Finite-State Calculus},
    author={Edmund Grimley-Evans},
    journal={Proceedings of ACL-EACL 97, Madrid, pp 452-459, 1997.},
    year={1997},
    archivePrefix={arXiv},
    eprint={cmp-lg/9711002},
    primaryClass={cmp-lg cs.CL}
}