# Finite automata for sum of digits?

How can I construct a finite automata ,which accepts numbers which has sum of digits = 3 ? Alphabet = {0,1,2,3}

i think this is it. if i have some mistakes let me know.

• This is incorrect, as it would not accept a string like $3210$, for which the digits have a sum of $6$, which is divisible by $3$. – Ben I. May 15 '17 at 18:23
• His demand was- has sum of digits of 3. Since 33 has 6 i believe yours is incorrect. Unless i did not understand the question. But you are right. Mine is incorrect either. – Omer Ben Haim May 15 '17 at 18:26
• Ah, I misread :) – Ben I. May 15 '17 at 18:30
• What's the purpose of accepting invalid sequences rather than halting? e.g. Why does 333 get accepted to state $q_4$ rather than halt at the second 3? I'm not claiming it's incorrect, it's just a format I haven't regularly seen so I was curious. It seems like it depends on your definition of Complete and Incomplete Automata. – ryan May 15 '17 at 18:41
• A FSM does not ever "halt" until it runs out of input. $q_4$ doesn't have a double-circle, so it is not an accept state. In fact, you may notice that there are no transitions out of $q_4$ - it is basically where the string goes to die - it is a "garbage state". Often, we don't bother to write out the transitions to the garbage state, but they are simply implied. – Ben I. May 15 '17 at 18:44

Define one state per sum achieved so far (i.e. $0,1,2,3,>3$).

Then from any state, it is obvious which is the next state.

In terms of regular expressions, you accept

$$0^*10^*10^*10^*|0^*10^*20^*|0^*20^*10^*|0^*30^*$$