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

Question

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

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

/foo/**/bar/*.baz

其中 ** 匹配 0 个或多个字符，* 匹配零个或多个非 / 的字符，所有其他字符均为字面意思。

有什么想法吗？

谢谢， 麦克

编辑:

我实现了一些似乎表现良好的东西，但尚未尝试正确性证明。你可以看到source和 unit tests

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) 到 (符号 r 上的 c, d) 存在，当且仅当 a ->r c 是 A 中的转换，并且 b ->r d 是 B 中的转换。
• (a, b) 是 AnB 中的开始状态，当且仅当 a 和 b 是分别是A和B。
• (a, b) 是 AnB 中的接受状态，前提是每个状态都是其各自 FA 中的接受状态。

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