测试两种常规语言的交集 [英] Testing intersection of two regular languages

问题描述

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

I want to test whether two languages have a string in common. Both of these languages are from a subset of regular languages described below and I only need to know whether there exists a string in both languages, not produce an example string.

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

The language is specified by a glob-like string like

/foo/**/bar/*.baz

其中**匹配0个或更多字符，*匹配零个或多个非/字符，所有其他字符均为文字.

where ** matches 0 or more characters, and * matches zero or more characters that are not /, and all other characters are literal.

有什么想法吗?

谢谢， 迈克

我实现了一些看起来效果不错的东西，但是还没有尝试正确性证明.您可以看到单元测试

I implemented something that seems to perform well, but have yet to try a correctness proof. You can see the source and unit tests

推荐答案

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

Build FAs A and B for both languages, and construct the "intersection FA" AnB. If AnB has at least one accepting state accessible from the start state, then there is a word that is in both languages.

构造AnB可能很棘手，但是我敢肯定有FA教科书对此进行了介绍.我会采用的方法是:

Constructing AnB could be tricky, but I'm sure there are FA textbooks that cover it. The approach I would take is:

• AnB的状态分别是A和B的状态的笛卡尔积. AnB中的状态写为(a, b)，其中a是A中的状态，而b是B中的状态.
• 转换(a, b) ->r (c, d)(意味着符号r上从(a, b)到(c, d)的转换)存在，前提是a ->r c是A的转换，而b ->r d是A的转换. B.
• (a, b)是AnB的开始状态，而a和b分别是A和B的开始状态.
• (a, b)是AnB中的接受状态，前提是每个都是其各自FA中的接受状态.

• The states of AnB is the cartesian product of the states of A and B respectively. A state in AnB is written (a, b) where a is a state in A and b is a state in B.
• A transition (a, b) ->r (c, d) (meaning, there is a transition from (a, b) to (c, d) on symbol r) exists iff a ->r c is a transition in A, and b ->r d is a transition in B.
• (a, b) is a start state in AnB iff a and b are start states in A and B respectively.
• (a, b) is an accepting state in AnB iff each is an accepting state in its respective FA.

这全是我的头上的事，因此完全未经证实！

This is all off the top of my head, and hence completely unproven!

这篇关于测试两种常规语言的交集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！