regex - シーケンスを受け入れる最短の正規表現を見つけるにはどうすればよいですか？

Question

シーケンスを受け入れる可能な限り最小の正規表現を見つける方法を探しています。

それを面白くするために、私は星（クリーネ閉包）を必要とせず、できればワイルドカードを必要としませんか？

たとえば、シーケンス：'aaaaaaaa'は'a ^ 8'によって受け入れられ、a^8はシーケンスを受け入れるための最短の式になります。

誰かがそのような表現を生成する方法を知っていますか？

Answer 1

通常、特定の文字列に一致する可能性のある規則的なパターンが大量に存在するため、文字列が大きくなるにつれて、目的の検索スペースは指数関数的に大きくなる可能性があります。

あなたの場合、検索ヒューリスティックを使用して、最適なソリューションを見つけて概算したり、管理したりすることができると思います。そのための簡単な解決策はないと思います（それは私の意見ですが）。

Answer 2

正規表現と決定性有限オートマトンが同等であるとすると、DFAを最小化するためのアルゴリズムのいずれかを使用して、特定の正規表現を最小化できます。もちろん、最初に正規表現を考え出す必要がありますが、1つの文字列のみを受け入れる必要がある場合は、その文字列の文字が状態になります。次に、そのDFAを最小化して、正規表現に変換できます。