First, I have tried to build a DFA over the alphabet $\sum = \{0,\dots, 9\}$ that accepts all decimal representations of natural numbers divisible by 3, which is quite easy because of the digit sum. For this I choose the states $Q = \mathbb{Z}/3\mathbb{Z}\cup\{q_0\}$ ($q_0$ to avoid the empty word), start state $q_0$, accept states $\{[0]_3\}$ and $\delta(q, w) =\begin{cases} [w]_3 &\mbox{if } q = q_0 \\ [q + w]_3 & \mbox{else } \end{cases}$

Of course, it doesn't work that way for natural numbers divisible by 43. For 43 itself, I would end in $[7]_{43}$, which wouldn't be an accepting state. Is there any way I can add something there or do you have other suggestions on how to do this? Thanks.

  • $\begingroup$ Maybe you could use the divisibility test for 43: savory.de/maths1.htm . Or perform actual division using the DFA. In either case, the DFA would be very complicated. Any reason why you want to do this? $\endgroup$
    – Paresh
    Jan 20 '13 at 9:15
  • 6
    $\begingroup$ Your question is a special version of that one. $\endgroup$
    – A.Schulz
    Jan 20 '13 at 10:58

If the string read has a certain decimal value, then reading the next digit changes that value: multiply by $10$ and add that digit. The DFA keeps track of that value modulo $43$. Thus, for $q\in \{0,1,\dots,42\}$ and $a\in \{0,1,\dots,9\}$ you do

$\qquad \delta(q,a) = (10\cdot q + a) \bmod 43$.

Note that the DFA does not actually perform the computation; the transition is hard-coded.

  • 1
    $\begingroup$ Final state is 0, initial state is 0 (or a new state that just makes the DFA not accept the empty string). $\endgroup$
    – vonbrand
    Feb 12 '14 at 1:56

Your Answer

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