Computing the Edit Distance between a Regular Language and a Context-free Language
Sang‐Ki Ko, Yo-Sub Han · 2012
We propose an algorithm for computing the edit distance between a regular language and a context-free language. The edit distance is generally defined as the smallest number of operations required to transform a string into the other. By computing the edit distance between two languages instead of strings, we estimate the similarity between a regular language and a context-free language, which are often used for pattern matching or parsing.