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

Question

我是自学正则表达式,并在网上发现了一个有趣的练习题,包括编写一个正则表达式来识别所有可被3整除的二进制数(只有这样的数字).说实话,问题是要为这样的场景构建DFA,但我认为使用正则表达式应该是等效的.

我知道有一个小规则来确定二进制数是否可被3整除:取数字中偶数位的1的数量,并减去数字中奇数位的1的数量 - 如果这等于零,该数字可被3整除(例如:偶数2个时隙中的110-1和奇数1个时隙中的1).但是,我在修改正则表达式方面遇到了一些麻烦.

我最接近的是意识到数字可以是0,所以这将是第一个状态.我还看到所有可被3整除的二进制数从1开始,所以这将是第二个状态,但我从那里被卡住了.有人可以帮忙吗？

Answer 1

遵循Oli Charlesworth所说的,您可以b通过某个除数来建立基数的可分性DFA d,其中DFA中的状态代表除法的其余部分.

对于你的情况(基数2 - 二进制数,除数d= 3 ₁₀):

请注意,上面的DFA接受空字符串作为可被3整除的"数字".这可以通过在前面再添加一个中间状态来轻松修复:

可以使用正常过程转换为理论正则表达式.

当您获得DFA时,可以轻松地转换为支持递归正则表达式的实用正则表达式.在CodeGolf.SE的这个问题中,这显示了(base b= 10,d= 7 ₁₀)的情况.

让我引用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>)

打破它,你可以看到它是如何构建的.的原子分组(或非回溯基,或它相当于一组占有性)被用来确保只有空字符串替代进行匹配.这是(?DEFINE)在Perl中模拟的技巧.然后将基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>)

Answer 2

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

当我们在余数为0的二进制数后面加0时，实际的十进制数将增加一倍。因为每个数字都在向更高的位置移动。 3t * 2 = 6t，它也能被 3 整除。

当我们在余数为0的二进制数后面加1时，实际的十进制数将加倍加1。因为每个数字都在移到更高的位置，后面跟着一个1； 3t * 2 + 1 = 6t + 1，余数为1。

当我们在余数为1的二进制数后面加1时，实际的十进制数会加一倍，余数为0； (3t + 1)*2 + 1 = 6t + 3 = 3(2t + 1)，它可以被 3 整除。

当我们在余数为1的二进制数后面加0时，实际的十进制数将增加一倍。余数为 2 (3t + 1)*2 = 6t + 2..

当我们在余数为 2 的二进制数后面加 0 时，余数将为 1。 (3t + 2)*2 = 6t + 4 = 3(2t + 1) + 1

当我们在余数为 2 的二进制数后面加 1 时，余数仍然是 2。 (3t + 2)*2 + 1 = 6t + 5 = 3(2t + 1) + 2.

余数为2的二进制数，无论加多少个1，余数永远是2。 (3(2t + 1) + 2)*2 + 1 = 3(4t + 2) + 5 = 3(4t + 3) + 2

所以我们可以用DFA来描述二进制数：

注意：边缘q2 -> q1应标记为 0。