Quarterly (March, June, September, December)
160 pp. per issue
6 3/4 x 10
2014 Impact factor:

Computational Linguistics

Paola Merlo, Editor
March 2000, Vol. 26, No. 1, Pages 17-44
(doi: 10.1162/089120100561610)
© 2000 Association for Computational Linguistics
Practical Experiments with Regular Approximation of Context-Free Languages
Article PDF (3.33 MB)

Several methods are discussed that construct a finite automaton given a context-free grammar, including both methods that lead to subsets and those that lead to supersets of the original context-free language. Some of these methods of regular approximation are new, and some others are presented here in a more refined form with respect to existing literature. Practical experiments with the different methods of regular approximation are performed for spoken-language input: hypotheses from a speech recognizer are filtered through a finite automaton.