parsing - 2つの正規言語の共通部分のテスト

Question

2つの言語に共通の文字列があるかどうかをテストしたいと思います。これらの言語は両方とも、以下で説明する正規言語のサブセットからのものであり、サンプルの文字列を生成するのではなく、両方の言語に文字列が存在するかどうかを知る必要があるだけです。

言語は、次のようなグロブのような文字列で指定されます

/foo/**/bar/*.baz

ここで、**0個以上の文字に*一致し、そうでない0個以上の文字に一致/し、他のすべての文字はリテラルです。

何か案は？

ありがとう、マイク

編集：

うまく機能しているように見えるものを実装しましたが、正当性の証明はまだ試していません。ソーステストと単体テストを見ることができます

score 10 · Accepted Answer

FAAとB両方の言語を作成し、「交差点FA」を作成しAnBます。AnB開始状態からアクセス可能な受け入れ状態が少なくとも1つある場合は、両方の言語の単語があります。

構築AnBは難しいかもしれませんが、それをカバーするFA教科書があると確信しています。私が取るアプローチは次のとおりです。

の状態は、それぞれとAnBの状態のデカルト積です。の状態が書き込まれます。ここで、はの状態であり、はの状態です。ABAnB(a, b)aAbB
遷移（シンボルから(a, b) ->r (c, d)の遷移があることを意味します）は、がの遷移であり、がの遷移である場合に存在します。(a, b)(c, d)ra ->r cAb ->r dB
(a, b)はAnBiffの開始状態でaあり、はとの開始状態です。bAB
(a, b)AnBそれぞれがそれぞれのFAの受け入れ状態である場合、は受け入れ状態です。

これはすべて私の頭のてっぺんから外れているので、完全に証明されていません！

score 2 · Accepted Answer

クイック検索を実行したところ、この問題は決定可能です（別名、実行可能です）が、それを実行するための適切なアルゴリズムはわかりません。1つは解決策です：

これを理解するのは少し難しいかもしれませんが、これは私が知っている唯一の方法です。

2 に答える 2