Computing the closest match of an automaton and a string I have a problem where I'm trying to find an efficient algorithm for approximate string matching for an input to the closest string match from an automaton (the input is assumed to be not accepting for the automaton). I've looked around and found Levenshtein Automaton but had trouble finding out how it would be implemented from my automaton.

Also, are there any other methods that would be suitable/worth looking at for my problem?
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.