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:
- Bibkey:
- 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)
- Copy Citation:
- PDF:
- https://aclanthology.org/1997.iwpt-1.19.pdf
Export citation
@inproceedings{nederhof-1997-regular, title = "Regular Approximations of {CFL}s: A Grammatical View", author = "Nederhof, Mark-Jan", editor = "Nijholt, Anton and Berwick, Robert C. and Bunt, Harry C. and Carpenter, Bob and Hajicova, Eva and Johnson, Mark and Joshi, Aravind and Kaplan, Ronald and Kay, Martin and Lang, Bernard and Lavie, Alon and Nagao, Makoto and Steedman, Mark and Tomita, Masaru and Vijay-Shanker, K. and Weir, David and Wittenburg, Kent and Wiren, Mats", booktitle = "Proceedings of the Fifth International Workshop on Parsing Technologies", month = sep # " 17-20", year = "1997", address = "Boston/Cambridge, Massachusetts, USA", publisher = "Association for Computational Linguistics", url = "https://aclanthology.org/1997.iwpt-1.19", pages = "159--170", 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.", }
<?xml version="1.0" encoding="UTF-8"?> <modsCollection xmlns="http://www.loc.gov/mods/v3"> <mods ID="nederhof-1997-regular"> <titleInfo> <title>Regular Approximations of CFLs: A Grammatical View</title> </titleInfo> <name type="personal"> <namePart type="given">Mark-Jan</namePart> <namePart type="family">Nederhof</namePart> <role> <roleTerm authority="marcrelator" type="text">author</roleTerm> </role> </name> <originInfo> <dateIssued>1997-sep 17-20</dateIssued> </originInfo> <typeOfResource>text</typeOfResource> <relatedItem type="host"> <titleInfo> <title>Proceedings of the Fifth International Workshop on Parsing Technologies</title> </titleInfo> <name type="personal"> <namePart type="given">Anton</namePart> <namePart type="family">Nijholt</namePart> <role> <roleTerm authority="marcrelator" type="text">editor</roleTerm> </role> </name> <name type="personal"> <namePart type="given">Robert</namePart> <namePart type="given">C</namePart> <namePart type="family">Berwick</namePart> <role> <roleTerm authority="marcrelator" type="text">editor</roleTerm> </role> </name> <name type="personal"> <namePart type="given">Harry</namePart> <namePart type="given">C</namePart> <namePart type="family">Bunt</namePart> <role> <roleTerm authority="marcrelator" type="text">editor</roleTerm> </role> </name> <name type="personal"> <namePart type="given">Bob</namePart> <namePart type="family">Carpenter</namePart> <role> <roleTerm authority="marcrelator" type="text">editor</roleTerm> </role> </name> <name type="personal"> <namePart type="given">Eva</namePart> <namePart type="family">Hajicova</namePart> <role> <roleTerm authority="marcrelator" type="text">editor</roleTerm> </role> </name> <name type="personal"> <namePart type="given">Mark</namePart> <namePart type="family">Johnson</namePart> <role> <roleTerm authority="marcrelator" type="text">editor</roleTerm> </role> </name> <name type="personal"> <namePart type="given">Aravind</namePart> <namePart type="family">Joshi</namePart> <role> <roleTerm authority="marcrelator" type="text">editor</roleTerm> </role> </name> <name type="personal"> <namePart type="given">Ronald</namePart> <namePart type="family">Kaplan</namePart> <role> <roleTerm authority="marcrelator" type="text">editor</roleTerm> </role> </name> <name type="personal"> <namePart type="given">Martin</namePart> <namePart type="family">Kay</namePart> <role> <roleTerm authority="marcrelator" type="text">editor</roleTerm> </role> </name> <name type="personal"> <namePart type="given">Bernard</namePart> <namePart type="family">Lang</namePart> <role> <roleTerm authority="marcrelator" type="text">editor</roleTerm> </role> </name> <name type="personal"> <namePart type="given">Alon</namePart> <namePart type="family">Lavie</namePart> <role> <roleTerm authority="marcrelator" type="text">editor</roleTerm> </role> </name> <name type="personal"> <namePart type="given">Makoto</namePart> <namePart type="family">Nagao</namePart> <role> <roleTerm authority="marcrelator" type="text">editor</roleTerm> </role> </name> <name type="personal"> <namePart type="given">Mark</namePart> <namePart type="family">Steedman</namePart> <role> <roleTerm authority="marcrelator" type="text">editor</roleTerm> </role> </name> <name type="personal"> <namePart type="given">Masaru</namePart> <namePart type="family">Tomita</namePart> <role> <roleTerm authority="marcrelator" type="text">editor</roleTerm> </role> </name> <name type="personal"> <namePart type="given">K</namePart> <namePart type="family">Vijay-Shanker</namePart> <role> <roleTerm authority="marcrelator" type="text">editor</roleTerm> </role> </name> <name type="personal"> <namePart type="given">David</namePart> <namePart type="family">Weir</namePart> <role> <roleTerm authority="marcrelator" type="text">editor</roleTerm> </role> </name> <name type="personal"> <namePart type="given">Kent</namePart> <namePart type="family">Wittenburg</namePart> <role> <roleTerm authority="marcrelator" type="text">editor</roleTerm> </role> </name> <name type="personal"> <namePart type="given">Mats</namePart> <namePart type="family">Wiren</namePart> <role> <roleTerm authority="marcrelator" type="text">editor</roleTerm> </role> </name> <originInfo> <publisher>Association for Computational Linguistics</publisher> <place> <placeTerm type="text">Boston/Cambridge, Massachusetts, USA</placeTerm> </place> </originInfo> <genre authority="marcgt">conference publication</genre> </relatedItem> <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.</abstract> <identifier type="citekey">nederhof-1997-regular</identifier> <location> <url>https://aclanthology.org/1997.iwpt-1.19</url> </location> <part> <date>1997-sep 17-20</date> <extent unit="page"> <start>159</start> <end>170</end> </extent> </part> </mods> </modsCollection>
%0 Conference Proceedings %T Regular Approximations of CFLs: A Grammatical View %A Nederhof, Mark-Jan %Y Nijholt, Anton %Y Berwick, Robert C. %Y Bunt, Harry C. %Y Carpenter, Bob %Y Hajicova, Eva %Y Johnson, Mark %Y Joshi, Aravind %Y Kaplan, Ronald %Y Kay, Martin %Y Lang, Bernard %Y Lavie, Alon %Y Nagao, Makoto %Y Steedman, Mark %Y Tomita, Masaru %Y Vijay-Shanker, K. %Y Weir, David %Y Wittenburg, Kent %Y Wiren, Mats %S Proceedings of the Fifth International Workshop on Parsing Technologies %D 1997 %8 sep 17 20 %I Association for Computational Linguistics %C Boston/Cambridge, Massachusetts, USA %F nederhof-1997-regular %X 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. %U https://aclanthology.org/1997.iwpt-1.19 %P 159-170
Markdown (Informal)
[Regular Approximations of CFLs: A Grammatical View](https://aclanthology.org/1997.iwpt-1.19) (Nederhof, IWPT 1997)
- Regular Approximations of CFLs: A Grammatical View (Nederhof, IWPT 1997)
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.