正则表达式匹配二进制3的倍数

Question

我想知道如何构建一个正则表达式来判断一个二进制数是否是3的倍数。我在这个帖子中阅读了Check if a number is divisible by 3，但他们没有使用正则表达式，并且某人绘制的图表是错误的（因为它不接受偶数）。我尝试过：((1+)(0*)(1+))(0)，但对于一些值它不起作用。希望你能帮助我。

更新： 好的，谢谢大家的帮助，现在我知道如何绘制NFA，这里我留下了图表和正则表达式：

在图表中，状态是10进制数模3的结果。

例如：要转到状态1，您必须拥有1，然后可以添加1或0，如果添加1，则会得到11（10进制为3），并且此数字模3为0，然后您将弧线绘制到状态0。

((0*)((11)*)((1((00) *)1) *)(101 *(0|((00) *1 *) *0)1) *(1(000)+1*01)*) *

另一个正则表达式也可以用，但这个更短。

非常感谢:)

- voodoo14

---

真的需要使用正则表达式吗？检查可被整除性会更容易。 - Zorgatone

它属于P问题还是NP问题？ - user1921241

要检查一个二进制数是否能被3整除，需要从右侧开始计算非零奇数位和非零偶数位的比特数。如果它们的差是3的倍数，则该数字可以被3整除。 - hb20007

Answer 1

我知道这是一个老问题，但仍然缺乏高效的答案，并且这个问题在谷歌上第一次出现了“二进制可被3整除的正则表达式”。

根据作者提出的DFA，可以通过简化二进制字符串通过DFA的路径来生成一个非常简短的正则表达式。

使用只有状态A的最简单的正则表达式是：

0*

包括状态B：

0*(11)*0*

包括状态C：

0*(1(01*0)*1)*0*

并且要注意回到状态A后，整个过程可以再次开始。

0*((1(01*0)*1)*0*)*

使用一些基本的正则表达式规则，这简化为

(1(01*0)*1|0)*

祝您愉快。

- Kert Ojasoo

---

这应该是被选择的那一个。 - Gayan Weerakutti

关于“基本正则表达式规则”，删除初始的0*的原因在这里解释：https://youtu.be/xLp36MhQ_D8?t=411 ... 至于| 0是从哪里来的，那是因为(a*b*)* = (a | b)*。 - hb20007

Answer 2

如果我可以推荐我的解决方案给这个代码高尔夫问题！它是一个生成正则表达式的JavaScript代码（可能效率低下，但完成了任务）来检查每个进制的可除性。在二进制中，它为3生成的正则表达式如下：/^((((0+)?1)(10*1)*0)(0(10*1)*0|1)*(0(10*1)*(1(0+)?))|(((0+)?1)(10*1)*(1(0+)?)|(0(0+)?)))$/ 编辑：与Asmor的版本相比，可能非常低效 :)

编辑2：此帖已是重复问题。

- Casey Chu

---

它涵盖了许多其他情况！ - BoltClock

Answer 3

对于一些正在学习和寻找如何做到这一点的人：

1. 观看此视频： https://www.youtube.com/watch?v=SmT1DXLl3f4&t=138s

2. 编写状态方程并使用Axden定理解决它们

3. 我所做的方式与用户@Kert Ojasoo指出的相同，结果如图所示。我希望我做得正确，因为我花了两天时间来解决它...

4. 

- Marcin

---

考虑到字符串可能很长且重复（请参考这个 Kata：https://www.codewars.com/kata/54de279df565808f8b00126a/train/java），完整的正则表达式应为：^(1(01*0)*1|0)*$ - Marcin

请不要将“谢谢”作为答案。相反，投票支持您认为有帮助的答案。-【来自审核】 - buddemat

你的回答与@KertOjasoo的回答没有任何区别，正如你自己所写的那样。请不要添加已经存在的答案。 - buddemat

Answer 4

n+2n = 3n。因此，相邻的两个二进制位设置为1表示3的倍数。如果相邻的1的数量是奇数，则不是3的倍数。

因此，我建议使用以下正则表达式：

(0*(11)?)+

- Asmor

---

实际上，我错了。两个相邻的1足以，但不是必需的，例如9 = 1001。我的错误。 - Asmor