Computing the closest match of an automaton and a string
You can adopt the usual dynamic program to compute the Levenshtein distance between a word $w$ and a regular language $L$ computed by some given NFA without $\epsilon$ transitions. Suppose $w$ has length $n$. For each $0 \leq \ell \leq n$ and state $s$ of the NFA, we will compute $A(\ell,s)$ which is the minimum Levenshtein distance between the $\ell$th prefix of $w$ and a word that causes the NFA to reach state $s$. This quantity is given by the following calculation, involving an auxiliary array $A'$:


$A(0,s)$ is the length of the shortest path from the initial state of the NFA to $s$ [insertion].
$A'(\ell+1,s)$ is the minimum of the following quantities:


$A(\ell,t)$ if there is a transition from $t$ to $s$ marked $w_{\ell+1}$.
$A(\ell,t)+1$ if there is some transition from $t$ to $s$ [substitution].
$A(\ell,s)+1$ [deletion].

$A(\ell+1,s)$ is the minimum of $A'(\ell+1,t)+\kappa(s,t)$ over all $t$, where $\kappa(s,t)$ is the length of the shortest path from $t$ to $s$ in the NFA [insertion].


Finally, the distance is the minimum of $A(n,s)$ taken across all accepting states $s$.

This calculation requires that you compute in preprocessing the all-pairs-shortest-path matrix for the directed graph underlying the NFA. Some of the quantities arising in the computation could be infinite.