patternMinor
DFA that accepts any integer $n$ such that $n \bmod 7 =1$
Viewed 0 times
suchdfaacceptsanybmodthatinteger
Problem
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.
Is there smart way to do it without a machine which has memory or completes operations? A hint would be greatly appreciated.
Solution
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$.
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$.
Context
StackExchange Computer Science Q#99101, answer score: 3
Revisions (0)
No revisions yet.