regex - 2 つの正規表現を取り、それらが等しいかどうかを判断するアルゴリズムを見つけようとしています

Question

2 つの言語 L1 と L2 を与えて、それらが同等かどうか (L1 = L2) を判断することで、アルゴリズムがどのようなものになるかを調べようとしています。

最初にDFAに変換してから、それぞれを最小限のDFAに減らす必要があると確信していますが、私が見つけたように思いつくのは驚くほど難しい..

また、L1 - L2 と L2 - L1 が空の場合、L1 = L2 であることもわかっています。

ここで理論が得意な人はいますか？

score 1 · Accepted Answer

re equality をテストするための合理的に効率的なアルゴリズムの説明は、次の場所にあります。

記事の参照を掘り下げて、効率は劣るが実装が容易な他のソリューションを見つけてください。

score 1 · Accepted Answer

これは概念的に単純な答えです (L1 と L2 が規則的であると仮定します)。

1) L1 と L2 の DFA D1 と D2 をそれぞれ検索します。

2) 受容状態/非受容状態を交換することにより、D1 と D2 から D'1 と D'2 を構築します (D'1 は正確に ~L1 を受け入れ、D'2 は ~L2 を受け入れることに注意してください。ここで ~ は「の補数」を意味します)。

3) 標準積の構成を 3 回使用して、正確に (L1 交差 ~L2) 結合 (L2 交差 ~L1) を受け入れる DFA を生成します。

4) パート 3 の DFA が文字列を受け入れるかどうかを確認するには、開始状態からの到達可能性について各受け入れ状態をチェックします。

5) パート 3 の DFA が任意の文字列を受け入れる場合、L1 <> L2. それ以外の場合、L1=L2

これを高速化するために使用できる膨大な数のヒューリスティックがありますが、概念的には、これがおそらく最も単純なアルゴリズムです。パート 3 の製品構成の参考資料として、Dexter Kozen による「Automata and Computability」があります。

2 に答える 2