2
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ You really ought to ask this question of your TA. They already understand their solution and can explain it to you. We'd have to figure out what they think is going on, figure out what you think is going on, figure out what the difference is, etc. $\endgroup$ Nov 13, 2018 at 19:06

1 Answer 1

2
$\begingroup$

Consider the case where $k=1$. In other words, we're allowing a single error. We take our base automaton and apply this "error-allowing transformation" to it.

The transformed automaton generally works as follows:

  • The state $(q, 0)$ means "the underlying automaton is in state $q$, and we haven't made an error yet".
  • The state $(q, 1)$ means "the underlying automaton is in state $q$, and we have made a single error".
  • From any state $(q, 0)$, we can make the "correct" transition, or make any "incorrect" transition (a transition meant for any other symbol) and change the $0$ to a $1$.
  • From any state $(q, 1)$, we can only make the "correct" transition. In other words, once we've made one mistake, we can't make any more!
  • If we reach either $(a, 0)$ or $(a, 1)$, where $a$ is an accepting state, then we accept.

Hopefully this makes sense; let me know in the comments if it doesn't.

Now the key is, this works for any base automaton. So if we want $k=2$, we can just apply this transformation once, and then apply the transformation again!

The states now look like $((q, 0), 0)$. If we reach the state $((a, 1), 1)$, then we've made exactly two errors. And once we've made exactly two errors (there are no more zeroes to turn into ones), we're not allowed to make any more errors, we have to follow the base automaton exactly.

And then you can apply the transformation again for $k=3$, and again for $k=4$, and so on, for any natural $k$. Induction! QED.

(Another way to prove it is to allow errors in every state $(q, \psi)$ as long as $\psi < k$. This way doesn't involve induction, and might be a bit easier to grasp, since you have a straightforward "error counter".)

$\endgroup$
4
  • $\begingroup$ But based on the specific construction of d', it doesn't explicitly prevent us from making any more errors. Any following input, erroneous or not, will keep us in a state that treats it as though we only had 1 error. At least, that's how I'm seeing. Mind telling me why this point of view is incorrect? Thank you. $\endgroup$
    – pikecha
    Nov 13, 2018 at 20:27
  • $\begingroup$ @pikecha Ah, check the transition rule again. We can only take "error transitions" if we're in the state $(q, 0)$. If we're in the state $(q, 1)$, we're not allowed to do that any more. $\endgroup$
    – Draconis
    Nov 13, 2018 at 21:01
  • $\begingroup$ Yeah, the way I was parsing that was that we are allowed to read any input (which necessarily includes erroneous) and yet still stay in a state as though we've made only one error at that point (...(q, 1), ..., 1). For whatever reason, I feel as though I understand this more if I keep it as (q, i) and have it be true as long as i <= k. $\endgroup$
    – pikecha
    Nov 14, 2018 at 7:45
  • $\begingroup$ @pikecha The crucial line is d'((q, 1), a) = {(d(q, a), 1)}. That is, if you've already made an error, you have to follow d (the original transition function) without modification. $\endgroup$
    – Draconis
    Nov 14, 2018 at 16:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.