Given some alphabet $\backslash$Sigma $,$ we define the operator between two

strings as the number of positions in which the strings and

differ. That is$,$

For instance $,,.$

Claim: The language

is regular.

dist

x$,$ y in $\backslash$Sigma $*$ x y

dist$($x$,$ y$)=\{$

n if $|$ x $|=|$ y $|$ and they differ in exactly n positions

$\backslash$infty if x $!=$ y

dist$($aa$,$ baa$)=\backslash$infty dist$($aab$,$ baa$)=2$ dist$($aba$,$ bab$)=3$

dist$\_2($L$)=\{$w in $\backslash$Sigma $*$ : $$x in L s$.$t$.$ dist$($x$,$w$)<=2$