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 here does not make much sense. since we might match super long strings, then having more errors seems ok. Maybe we can ask for the following:
LDM(L,ε) is the set of strings, such that if x in LDM(L,ε), then there is a y in L, such that distance between x and y is at most ε|y|.
LDM(L,ε) does not seem to be a regular language.
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 here does not make much sense. since we might match super long strings, then having more errors seems ok. Maybe we can ask for the following:
LDM(L,ε) is the set of strings, such that if x in LDM(L,ε), then there is a y in L, such that distance between x and y is at most ε|y|.
LDM(L,ε) does not seem to be a regular language.