parsing - 测试两种常规语言的交集

Question

我想测试两种语言是否有共同的字符串。这两种语言都来自下面描述的常规语言的子集，我只需要知道两种语言中是否存在字符串，而不是生成示例字符串。

语言由类似 glob 的字符串指定，例如

/foo/**/bar/*.baz

where**匹配 0 个或多个字符，并*匹配零个或多个非 字符/，并且所有其他字符都是文字。

有任何想法吗？

谢谢，迈克

编辑：

我实现了一些似乎表现良好的东西，但还没有尝试过正确性证明。你可以看到源代码和单元测试

Answer 1

为两种语言构建 FA ，A并B构建“交叉 FA” AnB。如果AnB至少有一个从起始状态可访问的接受状态，则存在两种语言中的单词。

构建AnB可能很棘手，但我确信有 FA 教科书涵盖它。我会采取的方法是：

• 的状态分别是和AnB的状态的笛卡尔积。状态 in写成where是 state in并且is a state in 。ABAnB(a, b)aAbB
• 一个转移(a, b) ->r (c, d)（意思是，有一个从符号(a, b)到的转移）存在当且仅当是 中的转移，并且是 中的转移。(c, d)ra ->r cAb ->r dB
• (a, b)是AnBiff中的开始状态，是a和b中的开始状态。AB
• (a, b)AnB当当且当每个都是其各自的 FA 中的接受状态时是接受状态。

这完全不在我的脑海中，因此完全未经证实！

Answer 2

我只是做了一个快速搜索，这个问题是可以确定的（也可以完成），但我不知道有什么好的算法可以做到这一点。一种是解决方案是：

1. 将正则表达式都转换为 NFA A 和 B
2. 创建一个 NFA，C，表示 A 和 B 的交集。
3. 现在尝试从 0 到 C 中状态数的每个字符串，看看 C 是否接受它（因为如果字符串更长，它必须在一个点重复状态）。

我知道这可能有点难以理解，但这是我知道的唯一方法。