regex - 正規表現の比較

Question

包摂、部分的に重複、互いに素な2つの正規表現を比較できる解決策はありますか？つまり、2つの正規表現を比較する方法を知りたいです。次に、正規表現1が正規表現2に含まれている場合、2つの正規表現を組み合わせることができます。

score 4 · Accepted Answer

A と B の 2 つの式があり、A が B の動作のサブセットと一致するかどうかを確認したいとします。

B の最小化された DFA を計算し、2 つの式を結合して A と B の和集合を作成し、その新しい式の最小化された DFA を計算する必要があります。これらの 2 つの DFA が等しい場合、A は B のサブセットと一致します。

本質的に、最小化されたオートマトンを構築するプロセスを経ずに、これを適切にチェックすることはできません。ただし、質問に対して検証可能な真の回答が得られます。

2 つの式を組み合わせるには、のような新しい式を作成し(A)|(B)ます。エンジンがサポートしている場合は、非キャプチャ型の括弧を置き換えることができます。

アルゴリズムをすべて実行することにした場合は、そのプロセスに関する一連の記事を書きました。

2 つのオートマトンを比較するには、状態と遷移が同じであることを確認するだけです。それらは正確に等しい必要があります。

1 に答える 1