algorithm - 2つの正規表現が同じ文字列に一致するかどうかを確認する方法はありますか？

Question

2つの正規表現があります。これらの2つの正規表現に同時に一致する特定の長さの文字列を作成できるかどうかを判断する必要があります。そのためのアルゴリズムが必要です。

文字列の長さは20文字を超えません。

Answer 1

場合によります。perl互換の正規表現（pcre）の場合、チューリング完全であるため、これは一般的に不可能です。一致が常に終了することを確認することさえできません。

チョムスキー階層で定義されている元の「クリーンな」形式のレギュラー言語の場合、それらは交差点の下で閉じられていることが知られています。これについては、このスレッドですでに説明しています。

交差点のNFAを取得するとすぐに、それに一致する文字列があるかどうかを簡単に確認できます。theraがNFAの最初から最後までのパスである場合、このパスの文字列は検索している文字列です。 、DFAの場合、アルゴリズムはここに示されています。NFAに適応させるのは簡単です。