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

发布时间：2020-12-14 06:22:20 所属栏目：百科来源：网络整理

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

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

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

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

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

对于你的情况(基数2 – 二进制数,除数d = 310)：

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

可以使用normal process转换为理论正则表达式.

当您获得DFA时,可以轻松地转换为支持递归正则表达式的实用正则表达式.这是针对CodeGolf.SE在this question中(基数b = 10,d = 710)的情况而示出的.

让我引用the regex in the answer by Lowjacker,用Ruby正则表达式编写：

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

打破它,你可以看到它是如何构建的.原子分组(或非回溯组,或行为占有的组)用于确保仅匹配空字符串替代.这是在Perl中模拟(？DEFINE)的技巧.然后,当数量除以7时,组A到G对应于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>)

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!