AI工具人

# 用正则表达式匹配3的任意倍数

``````^(([0369]|[147][0369]*[258])|([258]|[147][0369]*[147])([0369]|[258][0369]*[147])*([147]|[258][0369]*[258]))*\$
``````

## 构造DFA

``````0128%3 == (((((0 % 3)*10 + 1) % 3)*10 + 2)*10 + 8) % 3
``````

``````for i = 0 to N:
for j = 0 to N:
if i*10 + k) % n == :
建立一条状态Si到Sj的边
``````

## DFA推导出正则表达式

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

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

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

``````B = A[147][0369]* | A[258][0369]*[258][0369]* | B[147][0369]*[258][0369]*
``````

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

``````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]* )*
``````

## 任意DFA转正则表达式的方法

DFA转Regex的核心思想也很简单，逐个删除中间状态(非初始状态和终止状态)，删除过程中把经过这个状态的路径合并到其他路径上，举例如下：

``````L[p->r] = L[p-q] · star[L[q->q]] · L[q-r]
L[r->p] = L[r-q] · star[L[q->q]] · L[q-p]
``````

`star(L[s,s]) · L[s,f] · star(L[f,s] · star(L[s,s]) · L[s,f] + L[f,f])`

``````# 首先需要把两个状态间的多条边合并成1条
for i = 1 to n:
for j = 1 to n:
if i == j then:
L[i,j] := ε
else:
L[i,j] := ∅
for a in Σ:
if trans(i, a, j):
L[i,j] := L[i,j] + a
remove(k):
for i = 1 to n:
for j = 1 to n:
L[i,j] += L[i,k] . star(L[k,k]) . L[k,j]

# 逐个删除中间状态
for i = 1 to n:
if not(final(i)) and not(initial(i)):
remove(i)
``````

## 代码

``````public class DFA2regex {
private final static int INITSTATE = 0;
private final static int FINALSTATE = 0;
private final static Set<Integer> set = new HashSet<>();

// 生成DFA时我直接将多条边合并成了一条
private static Map<String, String> getDFA(int n) {
Map<String, List<String>> map = new HashMap<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < 10; k++) {
String key = key(i, j);
if (!map.containsKey(key)) {
}
if ((i*10 + k) % n == j) {
List<String> list = map.get(key);
}
}
}
}
Map<String, String> finalRes = new HashMap<>();
for (HashMap.Entry<String, List<String>> entry : map.entrySet()) {
String key = entry.getKey();
String val =  entry.getValue().stream().reduce("", String::concat);
if (val.length() > 1) {
val = "[" + val + "]";
}
finalRes.put(key, val);
}
return finalRes;
}

private static void remove(int k, int n, Map<String, String> dfa) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (set.contains(i) || set.contains(j)) {
continue;
}
dfa.put(key(i, j), concat(dfa.get(key(i, j)), dfa.get(key(i, k)), star(dfa.get(key(k, k))), dfa.get(key(k, j))));
}
}
}

private static String concat(String s1, String s2, String s3, String s4) {
String str1 = s1;
String str2 = s2 + s3 + s4;
if (str1.length() > 0 && str2.length() > 0) {
str1 += "|";
}
String res = str1 + str2;
if (res.contains("|") || res.contains("*")) {
return "(" + res + ")";
}
return res;
}

private static String star(String s) {
if (s.equals("") || s.equals("|")) {
return "";
}
return s + "*";
}

private static String key(int s, int e) {
return s + "_" + e;
}

public static void main(String[] args) {
int n = 4;
Map<String, String> dfa = getDFA(n);
for (int i = 0; i < n; i++) {
if (INITSTATE != i && FINALSTATE != i) {
remove(i, n, dfa);
}
}
System.out.println("^" + star(dfa.get("0_0")) + "\$");
}
}
``````

## 彩蛋

#### 1

``````^[0123456789]*\$
``````

#### 2

``````^([02468]|[13579][13579]*[02468])*\$
``````

#### 3

``````^(([0369]|[147][0369]*[258])|([258]|[147][0369]*[147])([0369]|[258][0369]*[147])*([147]|[258][0369]*[258]))*\$
``````

#### 4

``````^((([048]|[159][37]*[26])|([26]|[159][37]*[048])([26]|[159][37]*[048])*([048]|[159][37]*[26]))|(([37]|[159][37]*[159])|([26]|[159][37]*[048])([26]|[159][37]*[048])*([37]|[159][37]*[159]))(([159]|[37][37]*[159])|([048]|[37][37]*[048])([26]|[159][37]*[048])*([37]|[159][37]*[159]))*(([26]|[37][37]*[26])|([048]|[37][37]*[048])([26]|[159][37]*[048])*([048]|[159][37]*[26])))*\$
``````

#### 5

``````^(((([05]|[16][16]*[05])|([27]|[16][16]*[27])([27]|[16][16]*[27])*([05]|[16][16]*[05]))|(([38]|[16][16]*[38])|([27]|[16][16]*[27])([27]|[16][16]*[27])*([38]|[16][16]*[38]))(([38]|[16][16]*[38])|([27]|[16][16]*[27])([27]|[16][16]*[27])*([38]|[16][16]*[38]))*(([05]|[16][16]*[05])|([27]|[16][16]*[27])([27]|[16][16]*[27])*([05]|[16][16]*[05])))|((([49]|[16][16]*[49])|([27]|[16][16]*[27])([27]|[16][16]*[27])*([49]|[16][16]*[49]))|(([38]|[16][16]*[38])|([27]|[16][16]*[27])([27]|[16][16]*[27])*([38]|[16][16]*[38]))(([38]|[16][16]*[38])|([27]|[16][16]*[27])([27]|[16][16]*[27])*([38]|[16][16]*[38]))*(([49]|[16][16]*[49])|([27]|[16][16]*[27])([27]|[16][16]*[27])*([49]|[16][16]*[49])))((([49]|[16][16]*[49])|([27]|[16][16]*[27])([27]|[16][16]*[27])*([49]|[16][16]*[49]))|(([38]|[16][16]*[38])|([27]|[16][16]*[27])([27]|[16][16]*[27])*([38]|[16][16]*[38]))(([38]|[16][16]*[38])|([27]|[16][16]*[27])([27]|[16][16]*[27])*([38]|[16][16]*[38]))*(([49]|[16][16]*[49])|([27]|[16][16]*[27])([27]|[16][16]*[27])*([49]|[16][16]*[49])))*((([05]|[16][16]*[05])|([27]|[16][16]*[27])([27]|[16][16]*[27])*([05]|[16][16]*[05]))|(([38]|[16][16]*[38])|([27]|[16][16]*[27])([27]|[16][16]*[27])*([38]|[16][16]*[38]))(([38]|[16][16]*[38])|([27]|[16][16]*[27])([27]|[16][16]*[27])*([38]|[16][16]*[38]))*(([05]|[16][16]*[05])|([27]|[16][16]*[27])([27]|[16][16]*[27])*([05]|[16][16]*[05]))))*\$
``````

#### 6

``````^((((([06]|[17][39]*[28])|([28]|[17][39]*4)([06]|5[39]*4)*(4|5[39]*[28]))|(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*(([06]|[17][39]*[28])|([28]|[17][39]*4)([06]|5[39]*4)*(4|5[39]*[28])))|(((4|[17][39]*[06])|([28]|[17][39]*4)([06]|5[39]*4)*([28]|5[39]*[06]))|(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*((4|[17][39]*[06])|([28]|[17][39]*4)([06]|5[39]*4)*([28]|5[39]*[06])))((([06]|[39][39]*[06])|(4|[39][39]*4)([06]|5[39]*4)*([28]|5[39]*[06]))|((5|[39][39]*5)|(4|[39][39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*((4|[17][39]*[06])|([28]|[17][39]*4)([06]|5[39]*4)*([28]|5[39]*[06])))*((([28]|[39][39]*[28])|(4|[39][39]*4)([06]|5[39]*4)*(4|5[39]*[28]))|((5|[39][39]*5)|(4|[39][39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*(([06]|[17][39]*[28])|([28]|[17][39]*4)([06]|5[39]*4)*(4|5[39]*[28]))))|((((5|[17][39]*[17])|([28]|[17][39]*4)([06]|5[39]*4)*([39]|5[39]*[17]))|(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*((5|[17][39]*[17])|([28]|[17][39]*4)([06]|5[39]*4)*([39]|5[39]*[17])))|(((4|[17][39]*[06])|([28]|[17][39]*4)([06]|5[39]*4)*([28]|5[39]*[06]))|(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*((4|[17][39]*[06])|([28]|[17][39]*4)([06]|5[39]*4)*([28]|5[39]*[06])))((([06]|[39][39]*[06])|(4|[39][39]*4)([06]|5[39]*4)*([28]|5[39]*[06]))|((5|[39][39]*5)|(4|[39][39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*((4|[17][39]*[06])|([28]|[17][39]*4)([06]|5[39]*4)*([28]|5[39]*[06])))*((([17]|[39][39]*[17])|(4|[39][39]*4)([06]|5[39]*4)*([39]|5[39]*[17]))|((5|[39][39]*5)|(4|[39][39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*((5|[17][39]*[17])|([28]|[17][39]*4)([06]|5[39]*4)*([39]|5[39]*[17]))))(((([39]|5[39]*[17])|([06]|5[39]*4)([06]|5[39]*4)*([39]|5[39]*[17]))|(([17]|5[39]*5)|([06]|5[39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*((5|[17][39]*[17])|([28]|[17][39]*4)([06]|5[39]*4)*([39]|5[39]*[17])))|((([28]|5[39]*[06])|([06]|5[39]*4)([06]|5[39]*4)*([28]|5[39]*[06]))|(([17]|5[39]*5)|([06]|5[39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*((4|[17][39]*[06])|([28]|[17][39]*4)([06]|5[39]*4)*([28]|5[39]*[06])))((([06]|[39][39]*[06])|(4|[39][39]*4)([06]|5[39]*4)*([28]|5[39]*[06]))|((5|[39][39]*5)|(4|[39][39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*((4|[17][39]*[06])|([28]|[17][39]*4)([06]|5[39]*4)*([28]|5[39]*[06])))*((([17]|[39][39]*[17])|(4|[39][39]*4)([06]|5[39]*4)*([39]|5[39]*[17]))|((5|[39][39]*5)|(4|[39][39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*((5|[17][39]*[17])|([28]|[17][39]*4)([06]|5[39]*4)*([39]|5[39]*[17]))))*((((4|5[39]*[28])|([06]|5[39]*4)([06]|5[39]*4)*(4|5[39]*[28]))|(([17]|5[39]*5)|([06]|5[39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*(([06]|[17][39]*[28])|([28]|[17][39]*4)([06]|5[39]*4)*(4|5[39]*[28])))|((([28]|5[39]*[06])|([06]|5[39]*4)([06]|5[39]*4)*([28]|5[39]*[06]))|(([17]|5[39]*5)|([06]|5[39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*((4|[17][39]*[06])|([28]|[17][39]*4)([06]|5[39]*4)*([28]|5[39]*[06])))((([06]|[39][39]*[06])|(4|[39][39]*4)([06]|5[39]*4)*([28]|5[39]*[06]))|((5|[39][39]*5)|(4|[39][39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*((4|[17][39]*[06])|([28]|[17][39]*4)([06]|5[39]*4)*([28]|5[39]*[06])))*((([28]|[39][39]*[28])|(4|[39][39]*4)([06]|5[39]*4)*(4|5[39]*[28]))|((5|[39][39]*5)|(4|[39][39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*(([06]|[17][39]*[28])|([28]|[17][39]*4)([06]|5[39]*4)*(4|5[39]*[28])))))*\$
``````

## 参考资料

### 评论 1

1. #1

如果我说你牛，那是在侮辱你，你狠牛

匿名8个月前 (12-02)回复