你如何编写一个正则表达式来定义0和1的所有字符串,作为二进制数,表示一个3的倍数的整数.
一些有效的二进制数将是：
11 110 1001 1100 1111
使用DFA
here,我们可以通过以下方式制作正则表达式,其中A,B,C表示DFA的状态.
A = 1B + 0A B = 1A + 0C C = 1C + 0B C = 1*0B // Eliminate recursion B = 1A + 0(1*0B) B = 01*0B + 1A B = (01*0)*1A // Eliminate recursion A = 1(01*0)*1A + 0A A = (1(01*0)*1 + 0)A A = (1(01*0)*1 + 0)* // Eliminate recursion
导致PCRE正则表达式如下：
/^(1(01*0)*1|0)+$/
Perl测试/示例：
use strict;
for(qw(
11
110
1001
1100
1111
0
1
10
111
)){
print "$_ (",eval "0b$_",") ";
print /^(1(01*0)*1|0)+$/? "matched": "didnt match";
print "\n";
}
输出：
11 (3) matched 110 (6) matched 1001 (9) matched 1100 (12) matched 1111 (15) matched 0 (0) matched 1 (1) didnt match 10 (2) didnt match 111 (7) didnt match
