Dayaan M. answered • 10d
Computer Science Graduate with Computer Engineering Coursework
This is a nice problem because the proof gets short as soon as you spot what the state is actually remembering. The whole thing rests on one fact about binary numbers.
The observation. If x is a binary string and you append one more bit c, then
val(xc) = 2 · val(x) + c
That is simply what appending a digit does in base 2. Everything shifts left one place, which doubles the value, and the new bit lands in the ones place. Now look again at the transition function you were handed:
δ(i, c) = (2i + c) mod n
It is that exact same operation, carried out mod n. So the machine is tracking the value of the number it has read so far, but only ever storing the remainder mod n. That is the whole idea, and everything else is writing it down carefully.
What to actually prove. Do not attack the language statement head on. Prove the stronger and far more convenient claim about the extended transition function δ*, and the language result drops out in one line at the end.
Claim. For every x in {0,1}*, δ*(0, x) = val(x) mod n.
Proof, by induction on |x|.
Base case, |x| = 0. Then x is the empty string ε. By definition δ*(0, ε) = 0, the start state, and val(ε) = 0, so val(ε) mod n = 0 as well. The two agree.
Inductive step. Suppose the claim holds for some string x, so δ*(0, x) = val(x) mod n. Let c be any bit in {0,1}. Then
δ*(0, xc) = δ(δ*(0, x), c) [definition of δ*]
= δ(val(x) mod n, c) [inductive hypothesis]
= (2 · (val(x) mod n) + c) mod n [definition of δ]
= (2 · val(x) + c) mod n [see the note below]
= val(xc) mod n [the observation above]
which is precisely the claim for the string xc. By induction it holds for every string. ■
The note on that fourth line, because it is the step a grader will look for. Replacing val(x) with val(x) mod n inside the expression is legal because reduction mod n respects both addition and multiplication. Concretely, write val(x) = qn + r where r = val(x) mod n. Then 2 · val(x) + c = 2qn + 2r + c, and the 2qn term disappears mod n, leaving (2r + c) mod n. Do not leave this line out, since it is the only place the modular arithmetic does any real work.
Finishing the language statement. The accepting set is F = {0}, so for any string x,
x is in L(Mn) ⇔ δ*(0, x) is in F ⇔ δ*(0, x) = 0 ⇔ val(x) mod n = 0
where the last step is the claim. Therefore L(Mn) = {x | val(x) mod n = 0}, which is what you wanted. ■
A sanity check worth running before you write any of it up. Take n = 3 and feed the machine 110, which is 6. Start at 0: reading 1 sends you to (0 + 1) mod 3 = 1, reading 1 sends you to (2 + 1) mod 3 = 0, reading 0 sends you to (0 + 0) mod 3 = 0. You finish in state 0, so the string is accepted, and 6 really is divisible by 3. Now try 101, which is 5: you pass through 1, then 2, then land in 2, so it is rejected, and 5 leaves remainder 2. Tracing two or three strings like that is the quickest way to convince yourself the state genuinely is the remainder, which is the insight the induction then formalizes.
