-2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

enter image description here

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

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Ben I. May 15 '17 at 18:23
  • $\begingroup$ 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. $\endgroup$ – Omer Ben Haim May 15 '17 at 18:26
  • $\begingroup$ Ah, I misread :) $\endgroup$ – Ben I. May 15 '17 at 18:30
  • $\begingroup$ 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. $\endgroup$ – ryan May 15 '17 at 18:41
  • 2
    $\begingroup$ 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. $\endgroup$ – Ben I. May 15 '17 at 18:44
2
$\begingroup$

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^*$$

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