正则表达式匹配 3 的倍数

本文基本是知乎上正则表达式如何匹配 3 的倍数?这个问题的答案摘抄记录。

首先总结规律得到一个确定性有穷状态转换机DFA,如下

DFA转正则

我们记 A 为终止到状态 A 的字符串集合,BC 类似,那么可以列出三个方程:

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

根据正则语言的特性,可以推导出如下形式的方程:

L = LU|V => L = VU*

因此上面方程可以修改为:

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

将 (3) 代入 (1) (2) 得

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

然后把 (5) 代入 (4) 得:

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

加上 ^ 和 $ 就行了,放去测试,全部正确。

总结:

即学习了DFA,又学习了正则,真好

发表评论

电子邮件地址不会被公开。