2

正規表現と文脈自由文法の共通部分が空かどうかを出力するアルゴリズムを探しています。この問題は決定可能であることはわかっていますが、実装例 (疑似コード) が見つかりません。

可能であれば.NETでそのようなアルゴリズムを誰かが提供してくれますが、これは必須ではありません。この問題は「通常の交差点」とも呼ばれます。グーグルで調べても、幾何学的アルゴリズムまたはそれに関する理論しか得られません。

編集：

誰でも。私は本当にそれに固執していて、まだ何も見つかりません。

4

2 に答える 2

6

これは、私が思いついたアプローチのスケッチです。これでうまくいくと思いますが、PDA から CFG への非常に厄介な変換を使用するため、おそらく最善の方法ではありません。

正規表現を非決定論的有限オートマトン (NFA) に変換し、最小の決定論的有限オートマトン (DFA) に減らします。文脈自由文法 (CFG) をプッシュダウン オートモートン (PDA) に変換します。これらの最初のステップはすべて、よく知られた非常に単純なアルゴリズムです。

DFA と PDA の交差点を見てみましょう。これも PDA です。DFA には状態 S1、開始状態 s1、最終状態 F1、および形式 ((source,trigger),destination) の遷移 delta1 があり、PDA には状態 S2、開始状態 s2、最終状態 F2、および遷移があるとします。 ((source,trigger,pop),(destination,push)) 形式の delta2。新しい PDA には状態 S1 X S2 があり、各状態はペアでラベル付けされています。最終状態 F1 X F2 と開始状態 (s1,s2) があります。次にトランジションです。

delta2 の要素である各遷移 d、要素 s1 である各状態 s について、形式 ((s,d.trigger),?) の delta1 の要素である遷移 t を見つけます。新しいトランジション (((d.source, s), d.trigger, d.pop),((d.destination, t.destination),d.push)) を作成します。

この新しい PDA は、RE と CFG によって作成された言語の共通点を受け入れる必要があります。言語が空かどうかをテストするには、言語を CFG に戻す必要があります。そのためのアルゴリズムは面倒で大規模ですが、機能します。それが終わったら、各端子記号をマークします。次に、右側にのみマークされたシンボルがあるというルールを持つ各シンボルをマークし、それ以上シンボルをマークできなくなるまで繰り返します. 開始記号をマークできる場合、言語は空ではありません。それ以外の場合、言語は空です。

于 2011-01-04T16:15:28.473 に答える