You can build DFA using simple modular arithmetics.
We can interpret w
which is a string of k-ary numbers using a following rule
V[0] = 0
V[i] = (S[i-1] * k) + to_number(str[i])
V[|w|]
is a number that w
is representing. If modify this rule to find w mod N
, the rule becomes this.
V[0] = 0
V[i] = ((S[i-1] * k) + to_number(str[i])) mod N
and each V[i]
is one of a number from 0 to N-1, which corresponds to each state in DFA. We can use this as the state transition.
See an example.
k = 2, N = 5
| V | (V*2 + 0) mod 5 | (V*2 + 1) mod 5 |
+---+---------------------+---------------------+
| 0 | (0*2 + 0) mod 5 = 0 | (0*2 + 1) mod 5 = 1 |
| 1 | (1*2 + 0) mod 5 = 2 | (1*2 + 1) mod 5 = 3 |
| 2 | (2*2 + 0) mod 5 = 4 | (2*2 + 1) mod 5 = 0 |
| 3 | (3*2 + 0) mod 5 = 1 | (3*2 + 1) mod 5 = 2 |
| 4 | (4*2 + 0) mod 5 = 3 | (4*2 + 1) mod 5 = 4 |
k = 3, N = 5
| V | 0 | 1 | 2 |
+---+---+---+---+
| 0 | 0 | 1 | 2 |
| 1 | 3 | 4 | 0 |
| 2 | 1 | 2 | 3 |
| 3 | 4 | 0 | 1 |
| 4 | 2 | 3 | 4 |
Now you can see a very simple pattern. You can actually build a DFA transition just write repeating numbers from left to right, from top to bottom, from 0 to N-1.