二进制和十进制3的倍数的正则式【自动机构造法】

一 求二进制3的倍数的正则

二进制3的倍数的自动机表如下

其中Qi表示余3的结果，推出

A = A0 + B1（1）

B = A1 + C0（2）

C = B0 + C1

利用R = Q+RP => R=QP*的公式可推出C = B01*，代入（2）式可得B=A1(01*0)*，再代入（1）式可得二进制3的倍数的正则式 A = [0 | (01*0)*]*，简单的测试了一下0,11,110,1001均成立，另外在别处常看到用1((10*1)|(01*0))*10*作为二进制3的倍数的正则式

二 求十进制3的倍数的正则

十进制3的倍数的自动机表如下

推出

A = A[0369] | B[258] | C[147]

B = A[147] | B[0369] | C[258]

C = A[258] | B[147] | C[0369]

利用R = Q+RP => R=QP*的公式可推出

A = (B[258] | C[147])[0369]* (1)

B = (A[147] | C[258])[0369]* (2)

C = (A[258] | B[147])[0369]* (3)

然后分配率合并计算结果得十进制3的倍数的正则式

A = (| B[258] | (A[258] | B[147])[0369]*[147])[0369]*

  =   [0369]*

    | B[258][0369]*

    | A[258][0369]*[147][0369]*

    | B[147][0369]*[147][0369]*

  =   [0369]*

    | A[147][0369]*([147][0369]*[258][0369]*)*[258][0369]*

    | A[258][0369]*[258][0369]*([147][0369]*[258][0369]*)*[258][0369]*

    | A[258][0369]*[147][0369]*

    | A[147][0369]*([147][0369]*[258][0369]*)*[147][0369]*[147][0369]*

    | A[258][0369]*[258][0369]*([147][0369]*[258][0369]*)*[147][0369]*[147][0369]*

  = [0369]* (

                  [147][0369]*([147][0369]*[258][0369]*)*[258][0369]*

    | [258][0369]*[258][0369]*([147][0369]*[258][0369]*)*[258][0369]*

    |             [147][0369]*([147][0369]*[258][0369]*)*[147][0369]*[147][0369]*

    | [258][0369]*[258][0369]*([147][0369]*[258][0369]*)*[147][0369]*[147][0369]*

    | [258][0369]*[147][0369]* )*

  = [0369]* (( [147][0369]*

      | [258][0369]*[258][0369]*

      ) ([147][0369]*[258][0369]*)* (

        [258][0369]*

      | [147][0369]*[147][0369]*)

    | [258][0369]*[147][0369]* )*

十进制部分参考自正则表达式如何匹配 3 的倍数？ - Belleve的回答 - 知乎