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.
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.