如何找到接受序列的最短可能的reg exp？

Question

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

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

例如，序列：'aaaaaaaa'将被'a^8'接受并且^ 8将是接受序列的最短可能的表达。

有没有人知道如何产生这样的表达？

Answer 1

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

我认为，在你的情况下，你可以尝试使用一些search heuristic尝试和近似，甚至设法找到最佳的解决方案。我不认为有一个简单的解决方案（虽然这只是我的看法）。

Answer 2

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