The Hamming distance between two bit strings

x

and

y

(notation:

H(x,y)

) is the number of places at which they differ. For example,

H(011,110)=2

. (If

|x|!=|y|

, then their Hamming distance is infinite.) If

x

is a string and

A

is a set of strings, the Hamming distance between

x

and

A

is the distance from

x

to the closest string in

A

:\

H(x,A)=^( def )min_(yinA)H(x,y).

\ For any set

Asube{0,1}^(**)

and

k>=0

, define\

N_(k)(A)=^( def ){x|H(x,A)

\ the set of strings of Hamming distance at most

k

from

A

. For example,

N_(0)({000})={000},N_(1)({000})={000,001,010,100}

, and

N_(2)({000})={0,1}^(3)-{111}

.\ Prove that if

Asube{0,1}^(**)

is regular, then so is

N_(2)(A)

. (Hint: If

A

is accepted by a machine with states

Q

, build a machine for

N_(2)(A)

with states

Q\\\\times {0,1,2}

. The second component tells how many errors you have seen so far. Use nondeterminism to guess the string

yinA

that the input string

x

is similar to and where the errors are.)

The Hamming distance between two bit strings x and y (notation: H(x,y)) is the number of places at which they differ. For example, H(011,110)=2. (If x=y, then their Hamming distance is infinite.) If x is a string and A is a set of strings, the Hamming distance between x and A is the distance from x to the closest string in A : H(x,A)=defminyAH(x,y). For any set A{0,1} and k0, define Nk(A)=def{xH(x,A)k} the set of strings of Hamming distance at most k from A. For example, N0({000})={000},N1({000})={000,001,010,100}, and N2({000})={0,1}3{111}. Prove that if A{0,1} is regular, then so is N2(A). (Hint: If A is accepted by a machine with states Q, build a machine for N2(A) with states Q{0,1,2}. The second component tells how many errors you have seen so far. Use nondeterminism to guess the string yA that the input string x is similar to and where the errors are.)