Give a DFA for $\Sigma = \{0, 1, 2, 3, 4\}$ that recognizes strings over the alphabet $0, 1, 2, 3, 4$ which are integers with a digit sum of $6$ and may have leading zeros. For example, $1230$ should be in the language since $1 + 2 + 0 + 3 = 6$, and $0024$ or $24$ should be in the language since $0 + 0 + 2 + 4 = 6$, but $203$, $301$ and $2341$ should not be in the language since their digit sums are $5$, $4$ and $10$ respectively.
Asked
Active
Viewed 70 times
0
-
Do you have any ideas for constructing this: what could be the states, for example? – Joppy Oct 11 '17 at 12:42
-
possible this needs to be migrated to a CompSci SE. Not sure if there is a theoretical CS one though... – JMJ Oct 11 '17 at 13:04
-
Take states from 0 to 7 such that if the automaton is in state $i$ and the digit $j$ is entered, it goes to state $i+j$ or 7 whatever is smaller. Hope it helps. – Wuestenfux Oct 11 '17 at 15:23
-
@SZN $\texttt{cstheory.stackexchange.com}$ – Math1000 Apr 02 '18 at 18:43