Finite automata {0,...,9} that reads the digits of integer n (left to right) and accepts if n mod 7=1

Question

So if I understand correctly I need to make a graph with q nodes, but to me the algorithm of divisibility with 7 is way to complex, let alone having 1 remainder. Any help?

Answer 1

Going along the same lines as Ingix points out in the question's comments, there is a way to handle this properly without needing full division.

First, write a recursive program to solve the problem a digit at a time:

machine :: State -> [Digit] -> Result
machine 1     []     = Accept
machine _     []     = Reject
machine state (d:ds) = machine ((10*state + d) `mod` 7) ds

For the input 1286, this will be called as:

machine 0 [1, 2, 8, 6]

During processing of digits, there will be seven states from zero to six. The machine will start at state zero.

We can see that if there's no input remaining, state one is the only state that should accept. All others should reject.

If there is input remaining, the states can be wired to each other with the formula in the last line of the program above: $ state \to 10 state + digit \mbox{, reduced modulo } 7 $.

State transition table

Here's part of the state transition table:

┏━━━━━━┯━━━━━━━━━━━━━━━━┳━━━┳━━━┳━━━┳━━━┳━━━┳━━━┳━━━┓
┃ Input ╲ Initial state ┃ 0 ┃ 1 ┃ 2 ┃ 3 ┃ 4 ┃ 5 ┃ 6 ┃
┣━━━━━━━━┷━━━━━━━━━━━━━━╋━━━╇━━━╇━━━╇━━━╇━━━╇━━━╇━━━┫
┃     End of input      ┃ R │ A │ R │ R │ R │ R │ R ┃
┣━━━━━━━━━━━━━━━━━━━━━━━╉───┼───┼───┼───┼───┼───┼───┨
┃           0           ┃ 0 │ 3 │ 6 │ 2 │ 5 │ 1 │ 4 ┃
┣━━━━━━━━━━━━━━━━━━━━━━━╉───┼───┼───┼───┼───┼───┼───┨
┃           1           ┃ 1 │ 4 │ 0 │ 3 │ 6 │ 2 │ 5 ┃
┣━━━━━━━━━━━━━━━━━━━━━━━╉───┼───┼───┼───┼───┼───┼───┨
┃           2           ┃ 2 │ 5 │ 1 │ 4 │ 0 │ 3 │ 6 ┃
┣━━━━━━━━━━━━━━━━━━━━━━━╉───┼───┼───┼───┼───┼───┼───┨
┋                       ┋   ┊   ┊   ┊   ┊   ┊   ┊   ┋
┣━━━━━━━━━━━━━━━━━━━━━━━╉───┼───┼───┼───┼───┼───┼───┨
┃           9           ┃ 2 │ 5 │ 1 │ 4 │ 0 │ 3 │ 6 ┃
┗━━━━━━━━━━━━━━━━━━━━━━━┻━━━┻━━━┻━━━┻━━━┻━━━┻━━━┻━━━┛

There are many patterns in it that make filling it out easier.