来源：https://jex.im/programming/triple-regex.html

Regex Golf上有一道题名为 Triples，即要求用正则表达式匹配3的倍数，还有一道匹配7的倍数的练习题。这种问题如果人肉解决的话，相当于做一道包含几十个数的四则运算题，不管你怎么想，反正我小时候遇到五个数以上的四则运算题都是直接略过。小时候不好好学习，现在该怎么办呢？——现在我会写代码了啊。 解决方案其实很简单：写程序构造一个接受3的倍数的DFA，再将其转换成正则式即可。

Finite Automaton

术语听起来都好抽象，其实解决思路就像小学生做除法一样简单。比如我们如何判定4641是3的倍数？ 从左往右一个数一个数地计算，最后余0即可：

4641
4    % 3 => 1
16   % 3 => 1
 14  % 3 => 2
  21 % 3 => 0

一次读一个数字，然后输出一个余数，如果最后余0则表示OK。影响我们判断的有两个因素：上次运算结果的余数，当前读入的字符。自动机就是这样一种机器，开始处于一个状态，每次读入一个字符，然后输出一个新状态。所以上面的运算可以用下面的自动机执行过程表示，起始状态为0，余数即为输出状态：

  4
0 => 1

用人话来讲就是：上次余数为0时，遇到4则余1；上次余1时遇到6则还余1；……
数字只有10个，所以我们可以穷举，除3余数只有0、1、2三种可能，当余数为任意一个时，下一次遇到的数字只有10种可能， 全部情况列举成一张表：

教科书都喜欢画DFA流程图，我也用GraphViz将就画个（这么乱的图真能帮助理解吗）：

接下来其实就可以动手写程序自动生成这张表了：

/**
自动构造接受N的倍数的DFA
@return { fromState => { Char => toState } }
*/
function buildDFA(N) {
  var map={},i,208)">jto;
  // i 为 From State
  for i=0;<++) //FromState不会超过N，因为余数肯定小于N嘛
    j<10{ // j 为枚举Input Digit Char
      //当上次余i这次碰到j时，除N的余数即为输出状态
      to*10+) % ;
      map[]=||{})[;
    }
  return ;
}

这代码也太简单了，用JavaScript写的好处就是现在按下F12将代码贴进去运行下就能看到结果了。可生成这张表有什么用呢？再写个执行DFA的函数就大功告成了：