正規表現が別の正規表現と直交しているかどうかを判断するにはどうすればよいですか?

StackOverflow https://stackoverflow.com/questions/489095

  •  20-08-2019
  •  | 
  •  

質問

私の質問は、（簡略化した）例で説明するのが最も適切だと思います。

正規表現 1:

^\d+_[a-z]+$

正規表現 2:

^\d*$

正規表現 1 は 一度もない 正規表現 2 が一致する文字列と一致します。したがって、正規表現 1 が 直交 正規表現 2 に。

多くの人が私が何を意味するのか尋ねましたが、 直交 それを明確にしてみます:

させて S1 正規表現 1 が一致する文字列の (無限の) セットになります。S2 正規表現 2 が一致する文字列のセットです。正規表現 2 は正規表現 1 と直交しています もし S1 と S2 の交差点は空です。正規表現 ^\d_a$ は次のようになります。 直交していない 文字列「2_a」がセットS1にあるため そして S2.

2 つの正規表現が互いに直交しているかどうかをプログラムでどのように判断できるのでしょうか?

最良のケースは、次のようなメソッドを実装するライブラリです。

/**
 * @return True if the regex is orthogonal (i.e. "intersection is empty"), False otherwise or Null if it can't be determined
 */
public Boolean isRegexOrthogonal(Pattern regex1, Pattern regex2);
役に立ちましたか？

解決 12

私は最終的に私が探していた正確にライブラリを見つけました

dk.brics.automatonする

使用方法：

/**
 * @return true if the two regexes will never both match a given string
 */
public boolean isRegexOrthogonal( String regex1, String regex2 ) {
   Automaton automaton1 = new RegExp(regex1).toAutomaton();
   Automaton automaton2 = new RegExp(regex2).toAutomaton();
   return automaton1.intersection(automaton2).isEmpty();
}

実装がないと後方参照のような複雑な正規表現の機能をサポートできないことに留意すべきです。 「高速化Javaの正規表現パッケージ」のブログ記事を参照してください。その紹介 dk.brics.automatonするます。

他のヒント

「直交」することによって、あなたは、私はそれを取る「交差点が空集合である」意味ですか？

私は...通常の形で正規文法に変換し、それが空の言語だかどうかを確認し、その後、交差点のための正規表現を構築します。

その後、再び、私は理論家だ...

  

私は...通常の形で正規文法に変換し、それが空の言語だかどうかを確認し、その後、交差点のための正規表現を構築します。

これは大砲でスズメを撮影のように思えます。理由だけではなく、製品のオートマトンを構築し、受け入れる状態が初期状態から到達可能であるかどうかをチェックしませんか？それはまた、最初の正規表現を構築することなく、すぐにあなたの交差点に文字列を与えるでしょう。

  

私は多項式時間ソリューションがあることを知って驚く少しだろう、と私はそれが停止問題と等価であることを学ぶために、まったく驚かないだろう。

私は（縮退場合）指数時間で正規表現からDFAを作成する必要がそれを行う方法を知っています。すべてがあるので、停止問題に還元可能だが、停止問題は、のないののそれの

に還元可能です
  

は、最後の場合は、任意のREは、有限状態マシンに変換することができるという事実を使用することができます。彼らは、ノードの同じセットを持っている場合、2台の有限状態マシンは同じアークがこれらのノードを接続すると、同じである。

     

だから、あなたがのFSMにあなたのREを翻訳し、それらのFSMが等しくない場合、RESが直交している、私はあなたが直交するための定義として使用していると思うものを与えられます。

これは正しくありません。あなたは、エッジで標識された多重グラフの意味での非同型で2つのDFA（のFSM）を持っていますが、同じ言語を受け入れることができます。また、いない場合は、あなたのテストは、2つの正規表現を受け入れるかどうかを確認するだろうとした非は、同一のを、OPが望んでいるのに対し、非のオーバーラップの言語（空の交差点）。

<時間>

また、\ 1、\ 2、...、\ 9建設が正規ではないことに注意してください：それは連結、労働組合と*（クリーネ閉包）で表現することはできません。あなたが代入をバック含めたい場合は、私は答えが何であるかを知りません。また、目的の文脈自由な言語のための対応する問題は決定不能であるという事実である2つの文脈自由文法のG1及びG2を取り、L（G2）≠Oで∩真IFFのL（G1）が返さないアルゴリズムが存在しません

この質問が投稿されてから 2 年が経過しましたが、今ではここで「genex」プログラムを呼び出すだけでこれを判断できると言えることを嬉しく思います。 https://github.com/audreyt/regex-genex

$ ./binaries/osx/genex '^\d+_[a-z]+$' '^\d*$'
$

空の出力は、両方の正規表現に一致する文字列が存在しないことを意味します。重複がある場合は、重複のリスト全体が出力されます。

$ runghc Main.hs '\d' '[123abc]' 
1.00000000      "2"
1.00000000      "3"
1.00000000      "1"

お役に立てれば！

私はどのようなアルゴリズムを構築するためには考えている、またそれを実装する任意のライブラリの私は承知していることを言ってみましょう。しかし、私はすべて稀少は、任意の複雑さの一般的な正規表現のために存在していることを知って驚くことではないでしょう。

すべての正規表現は、あなたが好みなら、正規表現「によって一致」されているすべての文字列を、表現によって生成される、または可能なすべての文字列の正規言語を定義します。文字列の集合などの言語を考えます。ほとんどの場合、セットは無限大になります。あなたの質問は、正規表現によって与えられた二組の交差が空であるかどうかを尋ねられます。

少なくとも最初の近似に、私は無限のセットのためにあなたが持っているよりも時間がかかるであろう、セットを計算せずにその質問に答えるための方法を想像することはできません。私は限られたセットを計算し、パターンは他の正規表現によって必要とされるものを超えて詳述されているときに決定する方法があるかもしれないと思うが、それは簡単ではないでしょう。

たとえば、単純な表現の(ab)*と(aba)*bを検討してください。 abab、abababなど、彼らが働くことは決してありませんのでをチェックせず、最初の式からababababを生成し、その後停止することを決定しますアルゴリズムは何ですか？言語が互いに素であるときには、完了することはないので、あなただけの文字列を生成し、一致が見つかるまでチェックすることはできません。私は一般的なケースに働くだろう何かを想像することはできませんが、その後、この種のもので、私よりもはるかに優れた人々が存在します。

すべてのすべてで、これは難しい問題です。私はそこに多項式時間ソリューションである、と私は全くそれが停止問題と等価であることを知って驚くことはないだろうことを知って少し驚くだろう。正規表現はチューリング完全でされていないことを考えると、が、それは解決策が存在することを少なくとも可能と思われる。

fsmtools の有限状態マシン上での操作のすべての種類を行うことができ、あなたの唯一の問題はfsmtoolsが操作できる形式に正規表現の文字列表現に変換することです。これは単純な場合のために、間違いなく可能ですが、{先に、背後}表情などの高度な機能の存在下でトリッキーになります。

私はそれを使用したことがありませんが、

また、 OpenFst のを見ているかもしれません。これは、しかし、交差点をサポートしています。

  

\ 1、\ 2ビット上の優れた点は...それは文脈自由、そしてそう解くことができないのです。マイナーポイント：未EVERYTHINGは、例えば...プログラムの等価を停止したように還元可能..です - ブライアンPostow

[私がコメントに返信しています]

IIRC、a^n b^m a^n b^mは文脈自由ではない、そしてそれは同じだからそう(a\*)(b\*)\1\2のいずれかではありません。 ISTRの{ ww | w ∈ L }は素晴らしいが、regularの一つであるため、Lは「ナイス」であったとしても「素敵」されていない、context-freeます。

私は私のステートメントを変更：REのすべてのの停止問題に還元可能である; - ）

1つの正規表現は、同じ場所で相互に排他的な文字グループとして、いくつかの場合には些細なことができる互いに直交であることを証明します。最も単純な正規表現が、任意の場合、これは自明でない問題です。グループや後方参照の深刻な表現については、私は、これは不可能であり得ることを言うようにこれまで行くだろう。

私は信じている kdgregory あなたは補完するを意味する直交を使用している正しいです。

は、この正しいですか？

私なら次のようにします。

  • 次の構造のようなものを使用して、各正規表現を FSA に変換します。

    struct FSANode
{
    bool accept;
    Map<char, FSANode> links;
}
List<FSANode> nodes;
FSANode start;

これは簡単ではありませんが、単純な正規表現の場合はそれほど難しくないことに注意してください。

  • 次のような新しい結合ノードを作成します。

    class CombinedNode
{
    CombinedNode(FSANode left, FSANode right)
    {
        this.left = left;
        this.right = right;
    }

    Map<char, CombinedNode> links;
    bool valid { get { return !left.accept || !right.accept; } }

    public FSANode left;
    public FSANode right;
}

左側と右側で同じ文字をたどることに基づいてリンクを構築すると、新しい CombinedNode を作成する 2 つの FSANode が得られます。

次に、CombinedNode(leftStart, rightStart) から開始してスパニング セットを見つけます。有効でない CombinedNode がある場合、セットは「直交」していません。

DFAに各正規表現に変換します。 1 DFAの受け入れ状態から第二のDFAの開始状態にイプシロン遷移を作成します。あなたは、実際には、イプシロン遷移を追加することにより、NFAを作成しています。そして、DFAにNFAを変換します。開始状態が状態を受け入れ、状態が到達可能である受け入れない場合、2つの正規表現は、「直交。」ではありません（それらの交差が空でないからである。）

DFAへの正規表現を変換し、DFAにNFAを変換するための手順を知っているがあります。あなたは、手続きのためSipserによる「計算理論入門」などの著書を見て、あるいは単にウェブの周りに検索することができます。間違いなく、多くの学部生と卒業生が一つの「理論」クラスまたは別のためにこれを行うにはありませんでした。

私はあまりにもすぐに話を聞きました。何が出て動作しますが、あなたはDFAフォームにご希望の正規表現を変換することができるかどうやろうとしている何のための手順がありません、私のオリジナルのポストに語っています。

Sipserによる「計算理論入門」第2版：

あなたは私が私の最初の記事で言及した本の中で手順を見つけることができます。これは、脚注で詳細を、46ページです。

の手順は、次の2つのDFAの交差点で新しいDFAを与えるだろう。新しいDFAに到達受け入れる状態を持っていた場合、その後の交差点が非空でます。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top