In some applications, such as programs that check spelling, we may not need an exact match of
the pattern, only an approximate one. Once the notion of an approximate match has been made
precise, automata theory can be applied to construct approximate pattern matchers. As an
illustration of this, consider patterns derived from the original ones by insertion of one symbol.
Let L be a regular language on $Σ$ and define
$insert (L) =$ {$uav : a ∈ Σ,uv ∈ L$}.
In effect, $insert (L)$ contains all the words created from $L$ by inserting a spurious symbol
anywhere in a word.
(a) Given an nfa for $L$, show how one can construct an nfa for $insert (L)$.
(b) Discuss how you might use this to write a pattern-recognition program for $insert (L)$, using as
input a regular expression for $L$.
