Publication
Regular Approximation of CFLs: A Grammatical View
Mark-Jan Nederhof
In: Harry Bunt; Anton Nijholt (Hrsg.). Advances in Probabilistic and other Parsing Technologies. Pages 221-241, Kluwer Academic Publishers, 2000.
Abstract
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.