DFKI-LT - Regular Approximation of CFLs: A Grammatical View

Mark-Jan Nederhof
Regular Approximation of CFLs: A Grammatical View
in: Harry Bunt, Anton Nijholt (eds.):
1 Advances in Probabilistic and other Parsing Technologies, Pages 221-241, Kluwer Academic Publishers, 2000
 
We show that for each context-free grammar a new grammar can be constructed that generates a regular language. This construction differs from some existing methods of approximation in that use of a pushdown automaton is avoided. This allows better insight into how the generated language is affected.
 
Files: BibTeX, Nederhof:2000:RACa.pdf