# How do I prove that this language is regular?

I'm working on a problem that defines a language $$D_n$$, here is how $$D_n$$ is defined: "Consider the language $$D_n$$ of binary strings representing numbers divisible by some fixed n."

The problem is to "Prove that the language $$D_n$$ is regular"

Normally, I would just construct a DFA for the language which would prove that the language is regular. Unfortunately for this problem $$D_n$$ describes a separate language for every natural $$n$$.

I can still define a DFA for it easily as the transition function is given by $$\delta(S_{j},0)=S_{(2j) mod(n)}$$ $$\delta(S_{j},1)=S_{(2j + 1) mod(n)}$$ But I would have to prove that the construction is correct, and when the transition function is defined in this way I have no idea how to go about that.

So my other approach was to use Myhill Nerode Theorem because this problem comes from the MNT chapter of the book. I know if I can prove the number of equivalence classes in $$D_n$$ that I can state the Myhill Nerode theorem proving that a DFA exists for $$D_n$$ and thereby proving that the language is regular. But I don't know how to prove the number of equivalence classes when the language isn't given by a regular expression or a DFA.

My question is: Which one of these approaches, if any is on the right track? How can I prove the number of equivalence classes for a language that I don't have a regular expression or DFA for? Any other advice is welcome of course. Thank you for your time.

• On the Wikipedia page, the use example is indeed for $D_3$. This might inspire you maybe.. – Henno Brandsma Dec 5 '19 at 23:27
• Does the string $0^k1$ represents $1$? – J.-E. Pin Dec 6 '19 at 7:44

It shouldn't be too bad to show your DFA construction is correct. I would try to show that, on a string representing a number $$x$$, your DFA ends up in state $$S_j$$ where $$j\equiv x \pmod{n}$$, by induction on the string length. Then it ends in state $$S_0$$ iff $$x$$ is divisible by $$n$$.
But you can also apply the Myhill-Nerode theorem: If $$x \equiv y \pmod{n}$$ then $$2^k x + m \equiv 2^k y + m \pmod{n}$$ for any natural numbers $$k$$ and $$m$$, implying that any strings representing $$x$$ and $$y$$ have no distinguishing extension. Thus there are at most $$n$$ equivalence classes.