0
$\begingroup$

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.

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

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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