Abstract
We show that for each context-free grammar a new grammar can be constructed that generates a regular language. This construction differs from existing methods of approximation in that use of a pushdown automaton is avoided . This allows better insight into how the generated language is affected. The new method is also more attractive from a computational viewpoint.- Anthology ID:
- 1997.iwpt-1.19
- Volume:
- Proceedings of the Fifth International Workshop on Parsing Technologies
- Month:
- September 17-20
- Year:
- 1997
- Address:
- Boston/Cambridge, Massachusetts, USA
- Editors:
- Anton Nijholt, Robert C. Berwick, Harry C. Bunt, Bob Carpenter, Eva Hajicova, Mark Johnson, Aravind Joshi, Ronald Kaplan, Martin Kay, Bernard Lang, Alon Lavie, Makoto Nagao, Mark Steedman, Masaru Tomita, K. Vijay-Shanker, David Weir, Kent Wittenburg, Mats Wiren
- Venue:
- IWPT
- SIG:
- SIGPARSE
- Publisher:
- Association for Computational Linguistics
- Note:
- Pages:
- 159–170
- Language:
- URL:
- https://aclanthology.org/1997.iwpt-1.19
- DOI:
- Cite (ACL):
- Mark-Jan Nederhof. 1997. Regular Approximations of CFLs: A Grammatical View. In Proceedings of the Fifth International Workshop on Parsing Technologies, pages 159–170, Boston/Cambridge, Massachusetts, USA. Association for Computational Linguistics.
- Cite (Informal):
- Regular Approximations of CFLs: A Grammatical View (Nederhof, IWPT 1997)
- PDF:
- https://preview.aclanthology.org/teach-a-man-to-fish/1997.iwpt-1.19.pdf