为字符串 {0,1} 设计一个 DFA，当反转时，十进制等效于 2 mod 7

Question

为字符串 {0,1} 设计一个 DFA，当反转时，十进制等价于 2 mod 7？

Answer 1

首先，我们设计一个自动机，它接受一个字符串，在二进制中相当于 2 mod 7。

我们应该有七个声明。

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.

由于 7 是素数，因此此自动机的状态只有一个传入箭头，每个 0 和 1 正好有一个出向箭头。只需反转箭头，将 q2 设置为开始状态，将 q0 设置为最终状态，您就有了答案。

请注意，上面的构造适用于所有类似的问题，即使您更改基数或字母表，唯一的问题是它可能会成为非素数基数的 NFA。