2 つの任意の正規表現が等しいかどうかを調べる方法はありますか? 私には複雑な問題のように見えますが、DFA の単純化メカニズムか何かがあるのではないでしょうか?
質問する
7622 次
4 に答える
10
同等性をテストするには、式の最小DFAを計算し、それらを比較します。
于 2009-02-18T09:35:37.660 に答える
10
等価性のテスト可能性は、正規表現の古典的な特性の 1 つです。(NB Perl の正規表現やその他の技術的に非正規の超言語について本当に話しているのであれば、これは当てはまりません。)
RE を一般化された有限オートマトン A および B に変換し、A の受け入れ状態が B の開始状態への null 遷移を持ち、B の受け入れ状態が反転するように、新しいオートマトン AB を構築します。これにより、B で受け入れられるすべての文字列を除いて、A で受け入れられるすべての文字列を受け入れるオートマトンが得られます。
BA についても同じことを行い、両方を純粋な FA に減らします。FA に開始状態からアクセスできる受け入れ状態がない場合、FA は空の言語を受け入れます。AB と BA の両方が空であることを示すことができれば、A = B であることを示したことになります。
Editへー、そこにある巨大なエラーに誰も気付かなかったなんて信じられない - もちろん意図的なものだ:-p
前述のオートマトン AB は、前半が A によって受け入れられ、後半が B によって受け入れられない文字列を受け入れます。目的のAB を構築するプロセスは、少しトリッキーです。頭の中で思いつくことはできませんが、それが明確に定義されていることは知っています (そして、A の受け入れ状態と B の非受け入れ状態の結果を表す状態を作成する必要がある可能性があります)。
于 2009-02-18T10:03:12.600 に答える
2
これは、正規表現の意味に大きく依存します。他の投稿者が指摘したように、両方の式を最小限の DFA に減らすことは機能するはずですが、純粋な正規表現に対してのみ機能します。
現実世界の正規表現ライブラリ (特に後方参照) で使用される構造の一部は、規則的ではない言語を表現する力を与えるため、DFA アルゴリズムはそれらに対して機能しません。たとえば、正規表現 :([a-z]*) \1は、スペースで区切られた同じ単語の 2 回の出現に一致します ( a aandb bではなく、b anor a b)。これは、有限オートマトンではまったく認識できません。
于 2009-02-18T10:05:18.650 に答える
1
次の 2 つの Perlmonks スレッドでは、この質問について議論しています (具体的には、blokhead の回答を読んでください)。
于 2009-02-18T08:49:51.373 に答える