正则表达式为二进制倍数3

Question

我想知道如何构造一个正则表达式来知道基数2(二进制)中的数字是否是3的倍数.我在这个线程中读过检查一个数字是否可以被3整除但是它们不用正则表达式做,并且有人绘制的图表是错误的(因为它不接受偶数).我尝试过:((1 +)(0*)(1 +))(0)但它不适用于某些值.希望您能够帮助我.

更新:好的,谢谢大家的帮助,现在我知道如何绘制NFA,在这里我离开了图表和常规表达:

在图中,状态是基数10 mod 3中的数字.

例如:要进入状态1,你必须有1,然后你可以加1或0,如果你加1,你将有11(基数10为3),这个数字mod 3为0然后你绘制弧到州0.

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

而另一个正则表达式工作,但这更短.

非常感谢 :)

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)*

祝你今天愉快.

Answer 2

如果我可以为此代码高尔夫问题插入我的解决方案!它是一段JavaScript,可以为每个基础生成正则表达式(可能效率低下,但可以完成工作).

这是它在基数2中为可消除性产生的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:此外,这是这个问题的副本.