测试两种常规语言的交集

Question

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

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

<代码>/foo/**/bar/*.baz

其中 ** 匹配 0 个或多个字符，* 匹配零个或多个字符不是 /，所有其他字符都是文字。

有什么想法吗？

谢谢， 迈克

编辑：

我实现了一些似乎表现良好的东西，但尚未尝试正确性证明。您可以看到 源 和 单元测试

Answer 1

为两种语言构建 FA A 和 B，并构造“交集 FA”AnB。如果 AnB 至少有一个可从开始状态访问的接受状态，则存在一个同时使用两种语言的单词。

构造 AnB 可能很棘手，但我确信 FA 教科书会介绍它。我采取的方法是：

• AnB 的状态分别是 A 和 B 状态的笛卡尔积。 AnB 中的状态写作 (a, b)，其中 a 是 A 和 中的状态b 是 B 中的状态。
• 转换 (a, b) ->r (c, d) （意思是，存在从 (a, b) 到 (c, d) 符号 r 上的 存在，当且仅当 a ->r c 是 A 中的转换，并且 b - >r d 是 B 中的转换。
• (a, b) 是 AnB 中的开始状态，当且仅当 a 和 b 是 中的开始状态分别为 A 和 B。
• (a, b) 是 AnB 中的接受状态，当且仅当每个都是其各自 FA 中的接受状态。

这都是我的想法，因此完全未经证实！

Answer 2

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

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

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