regex - 相互に排他的な正規表現

Question

正規表現のリストがある場合、2 つの正規表現が同じ文字列に一致しないことを簡単に判断する方法はありますか?

つまり、リストは、すべての文字列について、リスト内の最大 1 つの項目が文字列全体と一致する場合にのみ有効です。

これを決定的に証明するのは非常に難しい (おそらく不可能でしょうか?) ようですが、このテーマに関する研究は見当たらないようです。

私が尋ねる理由は、正規表現を受け入れるトークナイザーに取り組んでおり、一度に 1 つのトークンのみが入力の先頭に一致するようにしたいからです。

Answer 1

純粋な正規表現 (コンテキストフリー言語やより複雑な言語を認識させる後方参照やその他の機能がない) を使用している場合、あなたが求めていることは可能です。できることは、各正規表現をDFAに変換してから（通常の言語は交差の下で閉じられているため）、それらを2つの言語の交差を認識するDFAに結合することです。その DFA に開始状態から受け入れ状態へのパスがある場合、その文字列は両方の入力正規表現によって受け入れられます。

これに関する問題は、通常の regex->DFA アルゴリズムの最初のステップは、正規表現を NFA に変換し、次に NFA を DFA に変換することです。しかし、最後のステップでは、DFA 状態の数が指数関数的に増加する可能性があるため、これは非常に単純な正規表現に対してのみ実行可能です。

拡張正規表現構文を使用している場合、すべての賭けはオフです。文脈自由言語は交差の下で閉じられていないため、この方法は機能しません。

Answer 2

正規表現に関するウィキペディアの記事には、次のように記載されています

与えられた 2 つの正規表現について、記述された言語が本質的に等しいかどうかを判断し、各表現を最小限の決定論的有限状態マシンに還元し、それらが同形 (同等) であるかどうかを判断するアルゴリズムを作成することができます。

しかし、それ以上のヒントはありません。

もちろん、あなたが求めている簡単な方法は、多くのテストを実行することですが、証明の方法としてのテストの欠点は誰もが知っています。

Answer 3

正規表現を見ただけでは、それを行うことはできません。

[0-9]とがある場合を考えてみましょう[0-9]+。これらは明らかに異なる式ですが、文字列「1」に適用すると、どちらも同じ結果になります。文字列「11」に適用すると、異なる結果が生成されます。

ポイントは、正規表現だけでは十分な情報ではないということです。結果は、正規表現とターゲット文字列の両方に依存します。