CFGとの正規表現交差点のアルゴリズム

Question

正規表現とContexフリー文法の交差点が空であるかどうかを出力するアルゴリズムを探しています。この問題は決定可能であることを知っていますが、実装の例を見つけることはできません（pseudocodeで）。

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

編集:

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

Answer 1

これが私に起こるアプローチのスケッチです。これはうまくいくはずだと思いますが、PDAからCFGへのひどく乱雑な変換を使用するので、おそらくそれを行うための最良の方法ではありません。

正規表現を非決定的有限オートマトン（NFA）に変換し、最小限の決定有限オートマトン（DFA）に減らします。コンテキストフリーグラマー（CFG）をプッシュダウンオートモトン（PDA）に変換します。これらの最初のステップはすべて、よく知られており、かなり単純なアルゴリズムです。

DFAとPDAの交差点を取ります。これもPDAです。 DFAには状態S1、State State S1、Final State F1、およびTransitions Form（（Source、Trigger）、Destination）があり、PDAにはS2、State State S2、Final State F2、およびTransitonsがあります。フォームのdelta2（（ソース、トリガー、ポップ）、（宛先、プッシュ））。新しいPDAには、各状態がペアでラベル付けされた状態S1 x S2があります。最終状態f1 x f2があり、開始状態（S1、S2）があります。今、移行のために。

各遷移dについて、Delta2の要素について、各状態s要素S1について、形式（（S、D.trigger）？）のdelta1の要素を遷移します。新しい移行（（（D.Source、S）、D.Trigger、D.Pop）、（（D.Destination、T.Destination）、D.Push））を作成します。

この新しいPDAは、REとCFGによって生成された言語の交差点を受け入れる必要があります。言語が空であるかどうかをテストするには、CFGに戻す必要があります。そのためのアルゴリズムは乱雑で大きいですが、機能します。それを行ったら、各端末シンボルをマークします。次に、右側にマークされたシンボルのみがあるルールがある各シンボルをマークし、これ以上シンボルをマークできなくなるまで繰り返します。スタート記号をマークすることができれば、言語は空ではありません。それ以外の場合、言語は空です。