二进制数被3整除的正则表达式

Question

我正在自学正则表达式，并在网上找到一个有趣的练习题，要求编写一个正则表达式来识别所有可被3整除的二进制数字（仅限这种数字）。老实说，这个问题要求构建一个DFA以解决这种情况，但我认为使用正则表达式同样可以实现。

我知道有一个小规则可用于确定一个二进制数字是否可被3整除：取数字的偶数位上的1的数量，减去数字的奇数位上的1的数量，如果结果等于零，则该数字可被3整除（例如：110 - 偶数位2上的1和奇数位1上的1）。但是，我在将此适应于正则表达式时遇到了一些麻烦。

我最接近的思路是意识到数字可以是0，因此这将是第一个状态。我还看到所有可被3整除的二进制数字都以1开头，所以这将是第二个状态，但我卡在那里了。请问有人能帮忙吗？

- John Roberts

---

你能为刚才描述的内容画出DFA吗？ - Oliver Charlesworth

@OliCharlesworth 不太是，没有。我接近的想法是意识到这个数字可以是0，所以那就是第一个状态。我还发现所有二进制数能被3整除的都以1开头，所以那就是第二个状态，但是我在这里卡住了。 - John Roberts

@JohnRoberts：确实。我认为这是因为它不能被描述为这样（假设你的技巧是正确的）；它需要跟踪偶数和奇数之间可能的任意差异，而这又需要任意数量的状态... - Oliver Charlesworth

@Dan：但是这与问题有什么关系呢？ - Oliver Charlesworth

@OliCharlesworth 同意。我认为鉴于我的技巧，这是不可能的。我想知道是否还有其他方法。 - John Roberts

Answer 1

根据Oli Charlesworth的说法，你可以构建一个DFA，用于判断基数为b的数能否被某个除数d整除，其中DFA中的状态表示除法的余数。

对于您的情况（基数为2 - 二进制数，除数d= 3₁₀）：

请注意，上面的DFA接受空字符串作为可被3整除的“数字”。这很容易通过在前面添加一个中间状态来修复:

将其转换为理论正则表达式可以使用常规过程完成。

一旦你得到了DFA，就可以在支持递归正则表达式的实现中轻松地将其转换为实际的正则表达式。这在（基数b= 10，d = 7₁₀）的情况下在CodeGolf.SE的这个问题中有所展示。

让我引用Lowjacker答案中的正则表达式, 它采用了Ruby正则表达式风格:

(?!$)(?>(|(?<B>4\g<A>|5\g<B>|6\g<C>|[07]\g<D>|[18]\g<E>|[29]\g<F>|3\g<G>))(|(?<C>[18]\g<A>|[29]\g<B>|3\g<C>|4\g<D>|5\g<E>|6\g<F>|[07]\g<G>))(|(?<D>5\g<A>|6\g<B>|[07]\g<C>|[18]\g<D>|[29]\g<E>|3\g<F>|4\g<G>))(|(?<E>[29]\g<A>|3\g<B>|4\g<C>|5\g<D>|6\g<E>|[07]\g<F>|[18]\g<G>))(|(?<F>6\g<A>|[07]\g<B>|[18]\g<C>|[29]\g<D>|3\g<E>|4\g<F>|5\g<G>))(|(?<G>3\g<A>|4\g<B>|5\g<C>|6\g<D>|[07]\g<E>|[18]\g<F>|[29]\g<G>)))(?<A>$|[07]\g<A>|[18]\g<B>|[29]\g<C>|3\g<D>|4\g<E>|5\g<F>|6\g<G>)

分解一下，你可以看到它是如何构建的。使用 原子 分组（或 非回溯 分组，或行为类似于 占有性）来确保仅匹配空字符串选项。这是模拟 Perl 中的 (?DEFINE) 的技巧。然后，组 A 到 G 对应于将该数字除以 7 的余数为 0 到 6 的部分。

(?!$)
(?>
  (|(?<B>4   \g<A>|5   \g<B>|6   \g<C>|[07]\g<D>|[18]\g<E>|[29]\g<F>|3   \g<G>))
  (|(?<C>[18]\g<A>|[29]\g<B>|3   \g<C>|4   \g<D>|5   \g<E>|6   \g<F>|[07]\g<G>))
  (|(?<D>5   \g<A>|6   \g<B>|[07]\g<C>|[18]\g<D>|[29]\g<E>|3   \g<F>|4   \g<G>))
  (|(?<E>[29]\g<A>|3   \g<B>|4   \g<C>|5   \g<D>|6   \g<E>|[07]\g<F>|[18]\g<G>))
  (|(?<F>6   \g<A>|[07]\g<B>|[18]\g<C>|[29]\g<D>|3   \g<E>|4   \g<F>|5   \g<G>))
  (|(?<G>3   \g<A>|4   \g<B>|5   \g<C>|6   \g<D>|[07]\g<E>|[18]\g<F>|[29]\g<G>))
)
(?<A>$|  [07]\g<A>|[18]\g<B>|[29]\g<C>|3   \g<D>|4   \g<E>|5   \g<F>|6   \g<G>)

- nhahtdh

Answer 2

我有另一种解决办法，我认为这更易于理解。 当我们将一个数除以3时，余数可能是0、1、2。 我们可以使用表达式3t来描述可被3整除的数字（t是自然数）。

---

当在二进制数末尾加上0且其余数为0时，实际十进制数会翻倍。因为每个数字都向高位移动了一位。 3t * 2 = 6t，这也能被3整除。

当在二进制数末尾加上1且其余数为0时，实际十进制数会翻倍再加1。因为每个数字都向高位移动了一位并跟着一个1； 3t * 2 + 1 = 6t + 1，余数为1。

---

当在二进制数末尾加上1且其余数为1时，实际十进制数会翻倍再加1，余数为0； (3t + 1) * 2 + 1 = 6t + 3 = 3(2t + 1)，这也能被3整除。

当在二进制数末尾加上0且其余数为1时，实际十进制数会翻倍，余数为2。 (3t + 1) * 2 = 6t + 2。

---

当在二进制数末尾加上0且其余数为2时，余数为1。 (3t + 2) * 2 = 6t + 4 = 3(2t + 1) + 1 当在二进制数末尾加上1且其余数为2时，余数仍为2。 (3t + 2) * 2 + 1 = 6t + 5 = 3(2t + 1) + 2 无论在二进制数中加入多少个1，如果其余数为2，则余数将永远为2。 (3(2t + 1) + 2) * 2 + 1 = 3(4t + 2) + 5 = 3(4t + 3) + 2

---

因此，我们可以使用DFA来描述二进制数： 注意：边缘q2 -> q1应标记为0。

- Han

---

为什么q2状态有两个转换都标记为1？我猜转换到q1的标记应该是0？ - David

Answer 3

二进制数可被3整除的分为3类：

1. 有两个连续的1或两个由偶数个0隔开的1，这些数字能够互相抵消。

(例如：11、110、1100、1001、10010、1111)

(对应十进制数：3、6、12、9、18、15)

2. 有三个由奇数个0隔开的1，这些三个数字也会互相抵消。

(例如：10101、101010、1010001、1000101)

(对应十进制数：21、42、81、69)

3. 一些包含第一种和第二种规则（包括相互嵌套）的组合。

(例如：1010111、1110101、1011100110001)

(对应十进制数：87、117、5937)

因此，符合这三条规则的正则表达式很简单:

0*(1(00)*10*|10(00)*1(00)*(11)*0(00)*10*)*0*

如何阅读它:

() 将其封装起来

* 表示前面的数字/组是可选的

| 表示选择括号内的两边的选项

- Reid Eric

---

请将您的正则表达式更正如下：0*(1(00)10|10(00)1(00)(1)*0(00)10)0，因为在右侧您可以创建任意数量的循环。 - Davide

Answer 4

您遇到的问题是，虽然您的技巧（可能）有效，但它不适用于实际的DFA（您必须跟踪偶数和奇数之间可能存在的任意差异，这将需要任意数量的状态）。

另一种方法是注意到（从MSB到LSB工作），在第i个字符x[i]之后，您的子字符串必须在模3算术中等于0、1或2；将此值称为S[i]。x[i+1]必须是0或1，这相当于乘以2并可选地加1。

因此，如果您知道S[i]和x[i+1]，则可以计算S[i+1]。这个描述听起来熟悉吗？

- Oliver Charlesworth