问题的提出

给定一个整数n,求出能用来匹配所有被n整除的二进制数的正则表达式(任意一个即可)

例如:

  • n = 1, regex = (0|1)*
  • n = 4, regex = (0|1)*00

分析

对于n为2^k的情况,由二进制数的表达方式可知,对应的正则表达式为(0|1)*0{k}

不难理解,每次二进制数左移一位,对应的值变为原来的两倍。

那么对于更一般的情况(n != 2^k)时,该怎么做呢?

一开始考虑通解会比较困难,那不如用一个具体存在的数字来作为例子——考虑n=7的情况。

在这种情况下,我们可以把所有的数字,按照与7的模的结果,分为7类,用State(0)代表当前的数能被7整除,用State(1)代表当前的数被7整除余数为1……

我们来查看一个简单状态的转移:

  • State = 0,
    • 如果下一个数字是1, 转移到状态 (0 * 2 + 1) mod 7 = 1
    • 如果下一个数字是0, 转移到状态(0 * 2) mod 7 = 0

显然我们可以总结出如下规律:

  • State = k,
    • 如果下一个数字是1, 转移到状态(k * 2 + 1) mod 7
    • 如果下一个数字是0, 转移到状态(k * 2) mod 7

易知,对于n=7, 有 2n = 14个转移线路和n = 7个状态

如果把它用图画出来,大概就是类似下面的这个样子:

这是一个有限状态自动机(deterministic finite automaton, DFA),那么现在问题就被转换成如何由DFA求其等价的正则表达式了。

这篇博客介绍了几个消除状态的方法

  • 归纳法,参见《自动机理论、语言和计算导论 第二版》
  • 消结消弧法
  • Arden’s Lemma 解方程(高斯消元)

以下采用的是归纳法+消除节点的方法来做。

当消除状态s时,自动机中所有经过s的状态都不存在了
可以把与s相关的状态划分成三类

  1. 假设 q1,q2,...,qn是s的前驱状态,记作集合Q

  2. p1, p2, ..., pm 是s的后继状态,记作集合P

  3. S是从s到s的环

当删除状态s时删除了所有涉及状态s的边,作为补偿,需要给p_i,q_j集合中引入

新的正则表达式 {q_j}S*{p_i}

新边 Arc(q_j, p_i, {q_j}S*{p_i})
该正则表达式需要与状态q_j -> p_i 上原有的表达式r_ij合并(如果没有,就设原来的表达式为空集)

这样说也许有点费解,结合图片也许更能理解

以下图片来源于《自动机理论、语言和计算导论 第二版》第三章(Introduction to Automata Theory, Languages, and Computation)

代码实现

想了下还是删掉了

如果你能找到的话,代码就在这里,只有聪明的 人才能看到……