我正在自学正则表达式,并在网上发现了一个有趣的实践问题,该问题涉及编写正则表达式以识别所有可被3整除的二进制数字(并且只有这样的数字)。老实说,这个问题要求为这种情况构造DFA,但我认为使用正则表达式同样可以实现。
我知道有一个简单的规则可以确定二进制数是否可被3整除:将数字中偶数位的位数除以数字中奇数位的位数-如果该位数等于零,则该数字可被3整除(例如:偶数2插槽中为110-1,奇数1插槽中为1)。但是,在将其调整为正则表达式时遇到了一些麻烦。
我最接近的是意识到这个数字可以是0,所以这将是第一个状态。我还看到所有可被3整除的二进制数都以1开头,因此这将是第二个状态,但是我被困在那里。有人可以帮忙吗?
最佳答案
按照Oli Charlesworth所说的,您可以通过将某个基本除数b
划分为d
来区分DFA,其中DFA中的状态代表该除法的其余部分。
对于您的情况(基数2-二进制数,除数d
= 310):
请注意,上面的DFA接受空字符串作为可被3整除的“数字”。这可以通过在前面添加一个其他中间状态来轻松解决:
可以使用normal process转换为理论正则表达式。
获得DFA后,就可以轻松地将其转换为支持递归正则表达式的实用正则表达式。对于来自CodeGolf.SE的this question中的(base b
= 10,d
= 710)情况显示。
让我引用用Ruby regex风格编写的the regex in the answer by Lowjacker:
(?!$)(?>(|(?<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>)
对其进行分解,您可以看到它的构造方式。原子分组(或非回溯组,或表现为所有格的组)用于确保仅匹配空字符串替代项。这是在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>)
关于regex - 二进制数可被3整除的正则表达式,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15330027/