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

Question

我正在尋找一種方法來查找接受序列的最小可能的正則表達式。

爲了讓它變得有趣，我不想要任何恆星（Kleene恆星），最好沒有通配符？

例如，序列：'aaaaaaaa'將被'a^8'接受並且^ 8將是接受序列的最短可能的表達。

有沒有人知道如何產生這樣的表達？

Answer 1

隨着字符串的增長，搜索空間會隨着字符串的增長而呈指數級增長，因爲通常會有大量的規則模式可以匹配給定的字符串。

我認爲，在你的情況下，你可以嘗試使用一些search heuristic嘗試和近似，甚至設法找到最佳的解決方案。我不認爲有一個簡單的解決方案（雖然這只是我的看法）。

Answer 2

鑑於正則表達式和確定性有限自動機是等價的，可以使用algorithms for the minimisation of DFAs中的任何一個來最小化給定的正則表達式。您當然仍然需要提出一個正則表達式來開始，但如果您只需要它接受一個字符串，那麼該字符串的字符就是狀態。然後，您可以最小化該DFA並將其轉換爲正則表達式。