An interesting theoretical problem that arises: Given a regular language L, define LD(L,k) to be the set of strings with Levenshtein distance at most k from some string in L. 1. Is LD(L,k) regular? (yes) 2. How hard is it to construct a regular expression(or DFA, NFA) of LD(L,k) given a regular expression(or DFA, NFA) of L? (probably it is something k times the original size in terms of NFA) I believe a constant k he…
If memory serves, it returns the number of deletes/inserts/edits. So what you mention can still be handled.