automata - 为字符串 {0,1} 设计一个 DFA，当它反转时相当于 2 mod 7？

Question

为字符串{ 0,1 }设计一个DFA，当反转时它 相当于 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.