问题的提出

给定一个整数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)

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
import scala.collection.mutable.ArrayBuffer
class RegualExpressionDivisibleN {
case class DFA(private val stateNum: Int) {
case class Arc(edge: (Int, Int), regexString: String)
case class State(index: Int, preList: ArrayBuffer[Int], postList: ArrayBuffer[Int])

val arcs: ArrayBuffer[ArrayBuffer[String]] = ArrayBuffer.fill(stateNum, stateNum)("")
val states: ArrayBuffer[State] = ArrayBuffer.empty[State]

def addArc(from: Int, to: Int, str: String): Unit = {
if (from != to) {
states(from).postList += to
states(to).preList += from
}
arcs(from)(to) = str
}

def init(): Unit = {
for (index <- 0 until stateNum) {
states += State(index, ArrayBuffer.empty[Int], ArrayBuffer.empty[Int])
}

for (index <- 0 until stateNum) {
addArc(index, (index * 2) % stateNum, "0")
addArc(index, (index * 2 + 1) % stateNum, "1")
}
}

def deleteArc(state: State, pre: Boolean, index: Int): Unit = {
val list = if (pre) state.preList else state.postList
val i = list.indexOf(index)
if (i > 0) list.remove(i, 1)
}

/**
* 当消除状态s时,自动机中所有经过s的状态都不存在了
* 可以把与s相关的状态划分成三类
* 1.假设 q1,q2,...,qn是s的前驱状态,记作集合Q
* 2.p1, p2, ..., pm 是s的后继状态,记作集合P
* 3. S是从s到s的环,且S∩Q = S∩P = empty
* 当删除状态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合并(如果没有,就设原来的表达式为空集)
*
* @param s 需要被消除的状态
* @return 消除s状态后的DFA
*/
def reduceState(s: Int): DFA = {

val state = states(s)

for (qi <- state.preList; pi <- state.postList) {
val q = states(qi)
val p = states(pi)
val Rpq = arcs(qi)(pi)
val qArc = arcs(qi)(state.index)
val pArc = arcs(state.index)(pi)
val sArc = arcs(state.index)(state.index)

val S = sArc.length match {
case 0 => ""
case 1 => s"$sArc*"
case _ => s"($sArc)*"
}

def genStr(s: String): String = if (s.contains("|")) s"($s)" else s

val Q = genStr(qArc)
val P = genStr(pArc)

val str = if (Rpq.length > 0) Array(genStr(Rpq), Q+S+P).mkString("|") else Q + S + P
deleteArc(q, pre = false, p.index)
deleteArc(p, pre = true, q.index)
addArc(q.index, p.index, str)
deleteArc(q, pre = false, state.index)
deleteArc(p, pre = true, state.index)
}
this
}

def finalState: String = {
s"^(${arcs(0)(0)})+" + "$"
}
}

def regexDivisibleBy(n: Int): String = {
if (n == 1) return s"(0|1)*"
val m = DFA(n)
m.init()
val res = (1 until n).foldLeft(m)((dfa, state) => dfa.reduceState(state))
res.finalState
}
}