二进制和十进制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]* )*
