I am assuming that you mean finite-state automaton (FSA) when you say
automaton. Actually, this can work for other automata, notably for
Push-Down Automata (PDA) and is a nice way to do syntax-error recovery
in programming languages compilers. But string matching is usually
defined with regular expressions.
The answer to your question is called Levenshtein distance and Viterbi
selection. The Levenshtein automata, as defined in wikipedia, will not
directly help you, but they are close to the idea. The point is that
you actually have 3 automata in this problem, and there are different
ways to combine them depending on what you want to achieve.
Here is a hopefully intuitive explanation.
I call $R$ the FSA that is supposed to do the string matching.
Levenshtein distance (or edit distance) to a word in $\mathcal L(R)$ can be computed
non-deterministically by a weighted non-deterministic FSA (NFA) $R_L$ that
is doing the following. It has the same number of states as $R$, and
all the transitions of $R$ with weight 0. Then for every transition in
$R$ labeled with input symbol $a$ it has an $\epsilon$-transition
between the same state, with a weight corresponding to the cost of a
missing $a$ in the input. For every state $q$, and every input symbol
$a$, $q$ has an $a$-transition to itself with a weight corresponding
to the cost of an extra $a$ in the input string. Finally, for any pair of
transitions $\delta(q,a)=q'$ and $\delta(q,b)=q''$ in $R$, add two
transitions $\delta(q,b)=q'$ and $\delta(q,a)=q''$, weighted respectively
by the cost of replacing $a$ by $b$, and replacing $b$ by $a$.
A computation of $R_L$ can recognize any word an give a distance for
that word to some word to be matched in $\mathcal L(R)$. It could at
the same time output the corrected word that has been approximated.
This does not help you very much, because what you want is a word with
the least cost.
So you have to simulate all possible non-deterministic computations,
each with its distance counter (and its corrected string), so as to
keep the best answers. Here, dynamic programming is your friend as any
prefix of a least cost computation is a least cost computation.
If your weighted NFA $R_L$ has $n$ states, there are only $n$
different states you may be in after reading some prefix $w$ of the
input. Since you are only interested in the closest match, you keep
only for each state the minimum value of the counter for all
computations on $w$ that lead to that state. That is only $n$
state-counter pairs to keep, and from which to do a transition at each
But what you are computing is only the edit distance, and you may want
a bit more than that: the string of the language your input is
actually approximating. This again is easy: add to each counter value
the corrected input string corresponding to that computational path.
So you keep triples, adding to each pair one of the corrected strings
that corresponds to a computation leading to that state-weight pair.
When the input has been scanned and all non-scanning transitions
followed, the string associated with accepting states are some of the
strings most closely approximated by the input. However, since they may not have the same cost, you want to keep only those with minimum cost. You get only some as
you keep only one string with each state. But it is possible to keep
So that is the general idea. Note that the algorithms for measuring
the distance for two strings, suggested by Alu's answer is just a
special case of this when the FSA recognizes only a singleton set, a
Now this can be obtained more simply by using classical cross product
of finite state automata. The idea is that the errors that you wish to
accept and correct, with cost, can be formalized by a weighted finite
state transducer (or GSM) $T$. Then the automaton you want is obtained by
a cross product construction between your initial automaton $R$ and
your transducer $T$.
The advantage of this formalization is that it defines easily many
different kinds of distances. corresponding to errors that you are
willing to accept, such as $a$ can replace $b$ only when following a
$c$, with cost $k$. But complex error systems are costly to compute
with because of the cross-product that increases the number of states.
I do not have much time right now for details, but I may be adding it