I had already been given the answer by the TA in class, but I don't understand it. I'm not asking for the answer on a homework problem or anything.
The problem:
The Hamming distance ("distance") of a word w to v of the same size is the number of positions wherein they differ. The distance between a w and L is the smallest such distance from a word chosen among L.
Let k be a natural number, and L a regular language. L' is the set of words w at a distance not greater than k from L. Show that L' is regular.
The way to go about this was to construct an automaton for such an L', and to do induction on k. If k = 0, then L' = L0 = L, and M0 = (Q0, E, delta0, q0, F0).
In general
Q is the set of states for an automaton accepting words with a distance at most k.
E is the alphabet among all machines and languages.
d is the tranisition function of Mk,
q0 is the start state for Mk
F is the set of final states for Mk.
The answer, according to the TA:
Assuming that the construction is valid for all i <= k, we can form M' as follows:
Q' = Q x {0, 1}, and **q'** is an element of Q'
q0' = (q0, 0)
d'((q, 0), a) = {(d(q, a), 0)} u {(d(q, b), 1) | b element of E}
d'((q, 1), a) = {(d(q, a), 1)}
F' = {q' = (q, t) | t = 0 or t = 1}
I really don't get this. To me, it seems that if I start off with less than k+1 errors then I'll be in a state (q1, 0) for some q1, and if I read 1 error then I'm put in a state (q2, 1) for some q2. If I am in a state (q1, 1) for some q1 and read anything, then I'll be in a state (q2, 1) for some q2.
If I start with reading the first letter of any input, then I start in (q0, 0), and if I read one error then I'm in (q1, 1), and if I read 50 errors then I'm in (q, 1) for some q, but if we wanted k to be, say, 5, then I've surpassed that.
I'm really confused here. I'd appreciate any help.
Thank you.