可被 5 整除的二进制数的正则表达式
Regular Expression for Binary Numbers Divisible by 5
我想为可被 5 整除的二进制数编写一个正则表达式。
我已经完成了可被 2 整除的二进制数和 3 的正则表达式，但我找不到 5 的正则表达式。
有什么建议吗？
2^0 = 1 = 1 mod 5
2^1 = 2 = 2 mod 5
2^2 = 4 = -1 mod 5
2^3 = 8 = -2 mod 5
2^4 = 16 = 1 mod 5
2^5 = 32 = 2 mod 5
... -1 mod 5
... -2 mod 5
所以我们有一个 1、2、-1、-2 模式。有两个只有数字符号交替的子模式：令n为数字，最低有效数字为0；奇怪的模式是
(-1)^(n)
甚至模式是
2x((-1)^(n))
那么，这个怎么用呢？
设原数为100011，将数位分为偶数和奇数两部分。分别对每个部分数字求和。奇数位之和乘以2。现在，如果结果能被偶数位之和整除，则原数能被5整除，否则不能整除。示例：
100011
1_0_1_ 1+0+1 = 2
_0_0_1 0+0+1 = 1; 1x2 = 2
2 mod(2) equals 0? Yes. Therefore, original number is divisible.
如何在正则表达式中应用它？在正则表达式中使用 callout 函数可以应用它。标注提供了一种在正则表达式模式匹配过程中将控制权临时传递给脚本的方法。
不过，ndn的答案更合适也更简单，所以我推荐使用他的答案。
(0|1(10)*(0|11)(01*01|01*00(10)*(0|11))*1)*
添加 ^$ 以使用正则表达式对其进行测试。 See it working here。
你可以建一个DFA and convert it to regular expression. The DFA was already built in another answer。您可以阅读它，它的解释非常好。
总体思路是删除节点，添加边。
变为：
使用此转换和我链接的答案中的 DFA，以下是获取正则表达式的步骤：
（编辑：请注意，标签 "Q3" 和 "Q4" 在图中被错误地交换了。这些状态表示模数 5 后的余数。）
然而，“^(0|1(10)*(0|11)(01*01|01*00(10)*(0|11))1)$" 匹配空字符串。
我想为可被 5 整除的二进制数编写一个正则表达式。
我已经完成了可被 2 整除的二进制数和 3 的正则表达式，但我找不到 5 的正则表达式。
有什么建议吗？
2^0 = 1 = 1 mod 5
2^1 = 2 = 2 mod 5
2^2 = 4 = -1 mod 5
2^3 = 8 = -2 mod 5
2^4 = 16 = 1 mod 5
2^5 = 32 = 2 mod 5
... -1 mod 5
... -2 mod 5
所以我们有一个 1、2、-1、-2 模式。有两个只有数字符号交替的子模式：令n为数字，最低有效数字为0；奇怪的模式是
(-1)^(n)
甚至模式是
2x((-1)^(n))
那么，这个怎么用呢？
设原数为100011，将数位分为偶数和奇数两部分。分别对每个部分数字求和。奇数位之和乘以2。现在，如果结果能被偶数位之和整除，则原数能被5整除，否则不能整除。示例：
100011
1_0_1_ 1+0+1 = 2
_0_0_1 0+0+1 = 1; 1x2 = 2
2 mod(2) equals 0? Yes. Therefore, original number is divisible.
如何在正则表达式中应用它？在正则表达式中使用 callout 函数可以应用它。标注提供了一种在正则表达式模式匹配过程中将控制权临时传递给脚本的方法。
不过，ndn的答案更合适也更简单，所以我推荐使用他的答案。
(0|1(10)*(0|11)(01*01|01*00(10)*(0|11))*1)*
添加 ^$ 以使用正则表达式对其进行测试。 See it working here。
你可以建一个DFA and convert it to regular expression. The DFA was already built in another answer。您可以阅读它，它的解释非常好。
总体思路是删除节点，添加边。
变为：
使用此转换和我链接的答案中的 DFA，以下是获取正则表达式的步骤：
（编辑：请注意，标签 "Q3" 和 "Q4" 在图中被错误地交换了。这些状态表示模数 5 后的余数。）
然而，“^(0|1(10)*(0|11)(01*01|01*00(10)*(0|11))1)$" 匹配空字符串。