起因

这是我在 CodeWars 上做到的一道题,挺有意思的,正好现在编译原理学到自动机,就记录一下。
题目链接:https://www.codewars.com/kata/5993c1d917bc97d05d000068
题目的意思就是要你对给定的 $n \left(1 \leq n \leq 18 \right)$ 构造一个正则表达式,这个正则表达式能判定一个二进制数是否能被 $n$ 整除。

思路分析

乍一看没什么思路,一个二进制数关于 $n$ 的整除性好像没有什么表象上的规律。
那么,如何解决这个问题呢?我们可以尝试构造一个 DFA(确定性有限状态自动机)来判定一个二进制数是否能被 $n$ 整除,然后再想办法将这个 DFA 转化成一个正则表达式就可以了。

首先,对于一个指定的 $n$,我们可以给我们的 DFA 设置 $n$ 个状态:$q_i \left( 0 \leq i \lt n \right)$,分别代表当前读取到的二进制数可以被 $i$ 整除。

然后让我们考虑状态之间的转移。假设当前的读到的二进制数为 $S$,$S$ 可以被 $i$ 整除,即当前我们处在 DFA 的 $q_i$ 状态下。
当下一个字符为 $0$ 的时候,新的二进制数即为 $ \overline{S}0 $,其值即为 $2S$。那么我们就可以得到此时的转移:$T(q_i, 0)=q_{2i\ \mathrm{mod}\ n}$。
同理,我们可以得到下一个字符为 $1$ 时的转移:$T(q_i, 1)=q_{\left(2i+1\right)\ \mathrm{mod}\ n}$。
最开始还没有读入字符的时候,我们可以认为当前的数为 $0$,$0$ 模 $n$ 的值为 $0$。所以 $0$ 为我们的 DFA 的初始状态。

举一个 $n=4$ 时的例子,根据上面的分析,我们可以画出如下的 DFA 来:

下面就是要将这个 DFA 化简,由 4 个节点化简到唯一的 1 个节点 $q_0$。
化简的思路是消点,如下图所示(图中的 $+$ 表示连接):

运用这种消点的方法,对于上面的 $n=4$ 的例子,我们可以将 $q_3$ 消掉,得到如下的 DFA:

继续将 $q_1$、$q_2$ 消掉,就得到了最终的结果:

再在最外面加上 Kleene 闭包,我们就得到了 $n=4$ 时的答案:
$$(0|(1((11*0|0)1)*(11*0|0)0))*$$

代码实现

下面我们对任意的 $n$ 实现一个构造程序。最近在学 Scala,代码就用 Scala 写了。

首先列出一些关于正则表达式的帮助函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def wrap(pattern: String, criterion: (String => Boolean) = _.length > 1): String =
if (criterion(pattern)) {
s"($pattern)"
} else pattern

def union(pattern1: String, pattern2: String): String = {
def checkWrap(pattern: String): Boolean = {
var depth = 0
for (ch <- pattern) {
if (ch == '|' && depth == 0) return true
else if (ch == '(') depth += 1
else if (ch == ')') depth -= 1
}
false
}

def unionWrap(pattern: String): String = wrap(pattern, checkWrap)

s"${unionWrap(pattern1)}|${unionWrap(pattern2)}"
}

def kleene(pattern: String) = s"${wrap(pattern)}*"

对于每一个 $q_i$,我们需要记录转移到 $q_i$ 的模式、从 $q_i$ 转移出去的模式和 $q_i$ 转移到自己的模式。
我们也要提供给状态添加转移的功能。如果新加的转移是转移向自己的,就仅修改 self,否则,需要修改自己的 out 和转移至的状态的 in。如果原转移已存在,则需要将新的模式与原来的模式并起来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class State(val q: Int) {
val in = mutable.Map.empty[State, String]
val out = mutable.Map.empty[State, String]
var self: Option[String] = None

def addTransition(state: State, pattern: String): Unit = {
if (state == this) {
self = self match {
case Some(orig) => Some(union(orig, pattern))
case None => Some(pattern)
}
} else {
val newPattern = out.get(state) match {
case Some(orig) => union(orig, pattern)
case None => pattern
}
out += (state -> newPattern)
state.in += (this -> newPattern)
}
}
}

下面一部是最关键的操作,即消点。
消点的时候,取转入转移与转出转移的笛卡尔积,将每一组构造成新的转移添加到状态机中。注意要将涉及欲消除点的转移删除掉。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def removeState(state: State): Unit = {
val selfPattern = state.self match {
case Some(pattern) => kleene(pattern)
case None => ""
}

for {
(in, patternIn) <- state.in
(out, patternOut) <- state.out
} {
in.out -= state
out.in -= state
in.addTransition(out, wrap(patternIn) + selfPattern + wrap(patternOut))
}
}

基础工作做好后,先构建初始的状态机:

1
2
3
4
5
val states: IndexedSeq[State] = (0 until n).map(new State(_))
states.foreach(state => {
state.addTransition(states((state.q * 2) % n), "0")
state.addTransition(states((state.q * 2 + 1) % n), "1")
})

然后开始消点。为了让最终的结果不要太长,这里采取了贪心的策略。
每一次取转入转移数与转出转移数的乘积最小的状态消除掉,这样就能最小化每一次添加的转移数。如果乘积相同,则取转移到自己的模式较短的,这样添加的转移的模式的长度也会较短。

1
2
3
4
5
6
val remains = mutable.Set(states.tail: _*)
for (_ <- 1 until n) {
val state = remains.minBy(state => state.in.size * state.out.size + state.self.getOrElse("").length)
removeState(state)
remains -= state
}

最后结果为 $q_0$ 转移到自己的模式的 Kleene 闭包:

1
def getRegex: String = kleene(states(0).self.get)

最后附上完整代码:

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
import scala.collection.mutable

class Builder(val n: Int) {

private class State(val q: Int) {
val in = mutable.Map.empty[State, String]
val out = mutable.Map.empty[State, String]
var self: Option[String] = None

def addTransition(state: State, pattern: String): Unit = {
if (state == this) {
self = self match {
case Some(orig) => Some(union(orig, pattern))
case None => Some(pattern)
}
} else {
val newPattern = out.get(state) match {
case Some(orig) => union(orig, pattern)
case None => pattern
}
out += (state -> newPattern)
state.in += (this -> newPattern)
}
}
}

private def wrap(pattern: String, criterion: (String => Boolean) = _.length > 1): String =
if (criterion(pattern)) {
s"($pattern)"
} else pattern

private def union(pattern1: String, pattern2: String): String = {
def checkWrap(pattern: String): Boolean = {
var depth = 0
for (ch <- pattern) {
if (ch == '|' && depth == 0) return true
else if (ch == '(') depth += 1
else if (ch == ')') depth -= 1
}
false
}

def unionWrap(pattern: String): String = wrap(pattern, checkWrap)

s"${unionWrap(pattern1)}|${unionWrap(pattern2)}"
}

private def kleene(pattern: String) = s"${wrap(pattern)}*"

private def removeState(state: State): Unit = {
val selfPattern = state.self match {
case Some(pattern) => kleene(pattern)
case None => ""
}

for {
(in, patternIn) <- state.in
(out, patternOut) <- state.out
} {
in.out -= state
out.in -= state
in.addTransition(out, wrap(patternIn) + selfPattern + wrap(patternOut))
}
}

private val states: IndexedSeq[State] = (0 until n).map(new State(_))
states.foreach(state => {
state.addTransition(states((state.q * 2) % n), "0")
state.addTransition(states((state.q * 2 + 1) % n), "1")
})

private val remains = mutable.Set(states.tail: _*)
for (_ <- 1 until n) {
val state = remains.minBy(state => state.in.size * state.out.size + state.self.getOrElse("").length)
removeState(state)
remains -= state
}

def getRegex: String = kleene(states(0).self.get)
}

object Divisible {
def main(args: Array[String]): Unit = {
(1 to 18).foreach(i => println(s"$i: ${new Builder(i).getRegex}"))
}
}

PS:我一开始的时候,没有对消点的顺序做考虑,在 $n=18$ 的时候输出的正则表达式长度高达 60 多万。原题说答案不能超过 5000 个字符,但我交了程序发现还是通过了。然后意识到这个 5000 大概是对程序长度的限制。Scala 版除我外只有一个人(冰封julao)交了通过的代码……我就拿冰冰的代码试了一下 $n=18$ 的情况,输出结果也高达 22 万。于是我就想了一些简单的优化手段。现在我这个程序输出的 $n=18$ 的结果甚至到了 5000 字符以内了,就算是要求正则长度小于 5000 也没有问题了。(但是 $n=17$ 的正则表达式长度还是超过了 6000,不管了(逃