25

2 つの正規表現を取り込んで、それらが同型かどうか (つまり、まったく同じ文字列セットに一致するかどうか) を判断するライブラリが必要です。たとえば、a|b は [ab] と同型です。

私が理解しているように、正規表現はNFAに変換でき、場合によってはDFAに効率的に変換できます。次に、DFA を最小限の DFA に変換できます。これは、私が正しく理解している場合は一意であるため、これらの最小限の DFA を比較して同等性を確認できます。すべての正規表現 NFA を DFA に効率的に変換できるわけではないことを認識しています (特に、真に「正規」ではない Perl 正規表現から生成された場合)。ありえない。

これを行うことについてオンラインでたくさんの記事や学術論文を目にします (また、学生にこれを行うように依頼するクラスのプログラミング課題もいくつかあります) が、この機能を実装するライブラリを見つけることができないようです。私は Python や C/C++ ライブラリを好みますが、どの言語のライブラリでもかまいません。そのようなライブラリがあるかどうか誰かが知っていますか? そうでない場合、誰かが私が出発点として使用できる近くにあるライブラリを知っていますか?

4

2 に答える 2

10

試したことはありませんが、Regexp:Compare for Perl は有望に見えます: 最初の言語が 2 番目の言語のサブセットである場合、2 つの正規表現は同等であり、逆の場合も同様です。

于 2012-03-07T20:33:48.817 に答える
1

Java 用のBrics オートマトン ライブラリはこれをサポートしています。正規表現を最小限の決定論的有限状態オートマトンに変換し、これらが同等かどうかを確認するために使用できます。

public static void isIsomorphic(String regexA, String regexB) {
    Automaton a = new RegExp(regexA).toAutomaton();
    Automaton b = new RegExp(regexB).toAutomaton();
    return a.equals(b);
}

このライブラリは、通常の言語を記述する正規表現に対してのみ機能することに注意してください。後方参照などのより高度な機能はサポートしていません。

于 2013-07-17T22:14:16.243 に答える