Practical Experiments with Regular Approximation of Context-Free Languages
Open Access
- 1 March 2000
- journal article
- Published by MIT Press in Computational Linguistics
- Vol. 26 (1), 17-44
- https://doi.org/10.1162/089120100561610
Abstract
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.Keywords
This publication has 11 references indexed in Scilit:
- Suffix languages in Lr parsingInternational Journal of Computer Mathematics, 1995
- Practical arbitrary lookahead LR parsingJournal of Computer and System Sciences, 1990
- Grammars, parsers, and memory limitationsLanguage and Cognitive Processes, 1986
- Parsing extended LR(k) grammarsActa Informatica, 1981
- Extending lookahead for LR parsersJournal of Computer and System Sciences, 1981
- TRANSDUCERS AND GRAMMARS AS THEORIES OF LANGUAGETheoretical Linguistics, 1981
- LR-regular grammars—an extension of LR(k) grammarsJournal of Computer and System Sciences, 1973
- An efficient context-free parsing algorithmCommunications of the ACM, 1970
- A note on phrase structure grammarsInformation and Control, 1959
- On certain formal properties of grammarsInformation and Control, 1959