Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question

migrated from cstheory.stackexchange.com Jan 20 '13 at 8:58

This question came from our site for theoretical computer scientists and researchers in related fields.

    
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? –  Paresh Jan 20 '13 at 9:15
4  
Your question is a special version of that one. –  A.Schulz Jan 20 '13 at 10:58

1 Answer 1

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.

share|improve this answer
1  
Final state is 0, initial state is 0 (or a new state that just makes the DFA not accept the empty string). –  vonbrand Feb 12 at 1:56

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.