It seems impossible for me to find a pattern for integers $n$ such that $$n \equiv 1 \quad(\bmod 7)$$ in order to construct this DFA.

Is there smart way to do it without a machine which has memory or completes operations? A hint would be greatly appreciated.

  • 1
    $\begingroup$ How are your integers $n$ encoded? Try to be as explicit as possible, since the answer would heavily depend on the details of the encoding. $\endgroup$ – Yuval Filmus Oct 25 '18 at 20:52
  • $\begingroup$ A DFA has memory. It's called the "state". You need 7 states, just below 3 bits. $\endgroup$ – gnasher729 Oct 27 '18 at 10:12

I assume you are talking about integers encoded in some base $b \geq 2$, and we're reading the integer from left to right.

An inductive hint: say we have read the number $n$ so far, and our inductive assumption is that we are in state $n \bmod 7$ (so we have 7 states). We read the digit $d$. Our next state should be $bn + d \bmod 7$. How do we correctly determine what state to go to, since we don't know $n$?

Well the trick is that while you don't know $n$, you do know $n \bmod 7$. And:

$$bn + d \equiv b(n \bmod 7) + d\mod 7$$

So for example, in base $10$, if we are in the state $3$ (meaning $n \equiv 3 \mod 7$) and we just read the digit $8$, our next state will be $10\cdot 3 + 8 \equiv 3 \mod 7$. In other words, state $3$ points to itself on reading digit $8$ in base $10$.


Place 7 nodes. Number them from 0 to 6. In Any time, in whatever node we are, represents the current number module 7. So starting node is 0. And note 0 is the accepting node.

For each node, there are 7 outgoing edges (from 0 to 6.) Say we are in node i; outgoing edge j from i, connects the node i to node (i*10+j) mod 7.


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.