The Hamming distance $H(x, y)$ between two bit strings x and y is the number of places at which they differ. For example, $H(011, 110) = 2$. (If $|x| \not= |y|$, then their Hamming distance is infinite.)
Given a language $A \subseteq \{0,1\}^*$, we write $N_k(A)$ to denote the set of strings at distance less than or equal $k$ from $A$, that is, $$N_K(A) = \{x \in \{0,1\}^*\;|\;\exists y(y \in A \text{ and }H(x,y) \leq k)\}$$
Prove that if a language $A \subseteq \{0,1\}^*$ is regular, then so is $N_2(A)$.
This problem is adapted from Automata and Computability by Dexter C. Kozen p302.
How would this be proven?
$$ \def\cA{\mathcal{A}} $$ Let $L$ be a regular language on the alphabet $\{0, 1\}$. Since $N_2(L) = N_1(N_1(L))$, it suffices to prove that $N_1(L)$ is regular. Let $\cA = (Q, A, \cdot, i, F)$ be the minimal automaton of $L$. For each state $p$, $q$ of $\cA$, let $L_{p, q}$ be the language accepted by $\cA$ with $p$ as initial state and $S$ as set of final states. I let you verify that $$ N_1(L) = L \cup \bigcup_{(p,q) \mid p \cdot 0 = q}L_{i,\{p\}}1 L_{q,F} \cup \bigcup_{(p,q) \mid p \cdot 1 = q}L_{i,p}0 L_{q,F} $$ It follows that $N_1(L)$ is regular.