如何构造匹配指定有限字符串集的最小DFA或最简正则表达式

你要解决的是有限字符串集合对应的最小DFA构建问题，属于有限正则语言的标准处理场景，成熟流程如下：

• 第一步：构建前缀树（Trie），将所有输入字符串插入前缀树，每个字符串的结束节点标记为终止状态。
• 第二步：用Hopcroft算法对前缀树对应的DFA执行最小化，得到的结果就是状态数最少、同时满足仅匹配输入集合字符串的最小DFA，完全符合你提出的「终结符数量最少」的最小定义。
• 第三步：如果需要输出你示例中展示的紧凑正则表达式形式，对最小化后的DFA使用状态消去法，即可导出最短的等效正则表达式。

你此前使用的朴素公共前后缀提取算法存在局限性，只能处理连续的公共前缀/后缀片段，无法识别合并嵌套可选结构、中间可选段这类场景，比如最后一组示例中存在的(|a|b)、(|c)嵌套可选段，朴素方法无法完成合并，自然无法得到最小结果。

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