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
- 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/auto-file-uploads/1997.iwpt-1.19.pdf