Problem 1.30

Consider the following problem:

1.30 Let C_n = { x | x is a binary number that is a multiple of n}. Show that for each n ≥ 1, the language C_n is regular.

Several people did not realize that problem 1.30 requires the representation of a number n in binary. Thus, for example, C₇ would include strings such as the following:

111
10101
11100

but would not include these strings:

1
110
11111

A machine for C_n can be constructed as follows:

Let M = (Q, Σ, δ, q_s, F) be defined as follows:

Q = { q_i | 0 ≤ i ≤ n}.
Σ = {0,1}.
δ(q_i, 0) = q_{(2*i mod n)}
δ(q_i, 1) = q_{((2*i + 1) mod n)}
q_s = q₀
F = {q₀}

If you don't want ε to be in the language, then add a separate start state q_s and transitions δ(q_s,0) = q₀, δ(q_s,1) = q₁.

The proof of this construction is by induction on the length of the string. One can assume the following facts about modular arithmetic:

(a + b) mod n = (a mod n) + (b mod n)
(a +* b) mod n = (a mod n) * (b mod n)