regex - 如何找到接受序列的最短的 reg exp？

Question

我正在寻找一种方法来找到接受序列的最小可能正则表达式。

为了让它变得有趣，我不想要任何星星（Kleene 星星），最好不要通配符？

例如，序列：'aaaaaaaa' 将被 'a^8' 接受，而 a^8 将是接受序列的最短表达式。

有谁知道如何生成这样的表达式？

Answer 1

随着字符串的增长，您所追求的搜索空间很可能会呈指数增长，因为通常有大量的规则模式可以匹配给定的字符串。

我认为在您的情况下，您可以尝试使用一些启发式搜索来尝试近似甚至设法找到最佳解决方案。我不认为有一个简单的解决方案（尽管这只是我的观点）。

Answer 2

鉴于正则表达式和确定性有限自动机是等价的，您可以使用任何用于最小化 DFA 的算法来最小化给定的正则表达式。当然，您仍然需要想出一个正则表达式来开始，但如果您只需要它接受一个字符串，那么该字符串的字符就是状态。然后，您可以最小化该 DFA 并将其转换为正则表达式。