测试两种常规语言的交集

Question

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

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

/foo/**/bar/*.baz

其中**匹配0个或更多字符,并*匹配零个或多个不是的字符,/所有其他字符都是字面值.

有任何想法吗？

谢谢,迈克

编辑:

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

Answer 1

构建FAs A和B两种语言,并构建"交叉点FA" AnB.如果AnB至少有一个接受状态可以从开始状态访问,那么就会出现两种语言的单词.

构建AnB可能很棘手,但我确信有FA教科书可以覆盖它.我将采取的方法是:

• 状态分别AnB是状态的笛卡尔积A和B.AnB写入状态,(a, b)其中a是状态A并且b是状态B.
• 如果ff 是转换,并且是转换,则存在转换(a, b) ->r (c, d)(意味着,从符号(a, b)到(c, d)符号的转换).ra ->r cAb ->r dB
• (a, b)是AnBiff 中的起始状态,并且分别是a和b中的起始状态.AB
• (a, b)处于接受状态AnB当且仅当每个处于其相应的FA的接受状态.

这一切都是我的头脑,因此完全未经证实!