automata - 文字列 {0,1} の DFA を設計します。逆にすると、10 進法で 2 mod 7 に相当しますか?

Question

文字列{ 0,1 } のDFAを設計します。逆にすると、 10 進数は2 mod 7 に相当し ますか?

Answer 1

First we design an automata that accepts a string which in binary is equivalent to 2 mod 7.

We should have seven stated.

q0 -> 0 -> q0
q0 -> 1 -> q1
...
qn -> 0 -> q(2n mod 7)
qn -> 0 -> q(2n+1 mod 7)
...
q6 -> 0 -> q5
q6 -> 1 -> q6

q0 is start state, q2 is final state.

Since 7 is prime, this automata has states with exactly one in-coming arrow and exactly one out-going arrow for each 0 and 1. Just reverse the arrows, make q2 the start state and q0 the final state and you have your answer.

Note that above construction works all similar type of problems, even if you change the base or alphabet, only thing is it might become NFA for non-prime bases.