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.