是否存在可生成任意等价正则表达式对的相关方法？

一、等价正则对生成的现有算法 #

标准正则（仅包含连接、选择、克莱尼闭包三种基础运算，无回溯引用、环视、占有量词等PCRE扩展特性）的等价性是可判定的，已经有成熟的落地算法：

• 等价性判定核心逻辑：将两个正则分别转换为非确定有限自动机(NFA)，再转为确定有限自动机(DFA)，对DFA做最小化处理后，若两个最小DFA完全同构，则两个正则等价。
• 批量生成等价对的思路：首先随机生成一个基础正则，按照下方的等价规则做1~N次改写，再用上述DFA校验逻辑确认改写后的表达式和原表达式等价，即可得到一组符合要求的测试用例。
• 注意：包含PCRE扩展特性的正则等价性属于不可判定问题，不存在通用解法，这类场景只能用固定等价规则生成测试用例。

二、常见正则等价规则列表 #

以下所有规则中r、s、t均指代任意合法正则表达式，ε指代空字符串，∅指代不匹配任何字符串的空集：

闭包相关等价规则 #

• r*r ≡ rr*
• (rs)*r ≡ r(sr)*
• r+ ≡ rr* ≡ r*r
• r? ≡ r|ε
• r** ≡ r*
• r++ ≡ r+
• r?? ≡ r?
• (r*)* ≡ r*

选择运算等价规则 #

• r|s ≡ s|r
• r|r ≡ r
• (r|s)|t ≡ r|(s|t)
• r|ε ≡ r?
• r|r* ≡ r*
• r|∅ ≡ r

连接运算等价规则 #

• (rs)t ≡ r(st)
• rε ≡ εr ≡ r
• r∅ ≡ ∅r ≡ ∅

分配律等价规则 #

• r(s|t) ≡ rs|rt
• (s|t)r ≡ sr|tr

括号与组合简化规则 #

• (r) ≡ r
• (r|s)* ≡ (r*s*)* ≡ (r*|s*)*
• (r*s)* ≡ ε|r(r|s)*
• (rs)* ≡ ε|r(sr)*s
• r*(s|r)* ≡ (s|r)*
• (r|s)*r(r|s)* ≡ (s|r)*r
• (r|s)(r|s)* ≡ (r|s)+

量词等价规则 #

• r{n,n} ≡ 连续n个r连接的表达式
• r{m,n} ≡ r{0,n}（当m=0时）
• r{m,} ≡ 连续m个r连接的表达式 + r*
• r{0,1} ≡ r?
• r{0,} ≡ r*
• r{1,} ≡ r+

字符类等价规则（POSIX标准场景） #

• [abc] ≡ a|b|c
• [^abc] ≡ 匹配所有不在{a,b,c}范围内的单个字符的正则
• [a-zA-Z0-9_] ≡ \w
• [^a-zA-Z0-9_] ≡ \W
• [0-9] ≡ \d
• [^0-9] ≡ \D
• [ \t\n\r\f] ≡ \s
• [^ \t\n\r\f] ≡ \S

锚点等价规则 #

• ^r$ ≡ 仅匹配完整输入等于r的正则
• \br\b ≡ 匹配被单词边界包围的r的正则

你可以基于上述规则随机组合改写基础正则，生成任意多的等价测试用例，改写后可以用最小DFA同构校验确认等价性，避免规则组合出错。

内容的提问来源于stack exchange，提问作者user2852699