正则表达式定义一些二进制序列

Question

你如何编写一个正则表达式来定义0和1的所有字符串,作为二进制数,表示一个3的倍数的整数.

一些有效的二进制数将是:

11
110
1001
1100
1111

Answer 1

在这里使用DFA 我们可以通过以下方式制作正则表达式,其中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

Answer 2

将数字除以3时,只有三个可能的余数(0,1和2).你的目标是确保余数为0,因此是三的倍数.

这可以通过具有三种状态的自动机完成:

• ST0,3的倍数(0,3,6,9,....).
• ST1,3加1(1,4,7,10,......)的倍数.
• ST2,3加2的倍数(2,5,8,11,...).

现在想想任何非负数(这是我们的域)并将其乘以2(将二进制零加到最后).过渡是:

ST0 -> ST0 (3n * 2 = 3 * 2n, still a multiple of three).
ST1 -> ST2 ((3n+1) * 2 = 3*2n + 2, a multiple of three, plus 2).
ST2 -> ST1 ((3n+2) * 2 = 3*2n + 4 = 3*(2n+1) + 1, a multiple of three, plus 1).

还要考虑任何非负数,将其乘以2然后加一(将二进制加到最后).过渡是:

ST0 -> ST1 (3n * 2 + 1 = 3*2n + 1, a multiple of three, plus 1).
ST1 -> ST0 ((3n+1) * 2 + 1 = 3*2n + 2 + 1 = 3*(2n+1), a multiple of three).
ST2 -> ST2 ((3n+2) * 2 + 1 = 3*2n + 4 + 1 = 3*(2n+1) + 2, a multiple of three, plus 2).

这个想法是,最后,你需要在状态ST0完成.然而,考虑到可以存在任意数量的子表达式(和子子表达式),它不易于简化为正则表达式.

您需要做的是允许从ST0到ST0的任何转换序列然后重复它们:

归结为两个RE序列:

ST0 --> ST0                                      :  0+
    [0]
ST0 --> ST1 (--> ST2 (--> ST2)* --> ST1)* --> ST0:  1(01*0)*1
    [1]     ([0]     ([1]    )* [0]    )* [1]

还是正则表达式:

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

这捕获了三倍的倍数,或者至少是我测试的前十个.你可以尽可能多地尝试,他们都会工作,这是数学分析的美妙而不是轶事证据.