测试两种常规语言的交集

构建FAS A 和 B 对于两种语言,并构造“交集fa” AnB . 如果 ANB公司 至少有一个可从开始状态访问的接受状态,那么两种语言中都有一个单词。

建设 ANB 可能会很棘手,但我相信有一些FA教科书可以涵盖它。我会采取的方法是:

• 状态 ANB 是下列状态的笛卡尔积 一 和 乙 分别。一种状态 ANB 是书面的 (a, b) 在哪里? a 是一种状态 一 和 b 州是否处于 乙 .
• 过渡期 (a, b) ->r (c, d) (意思是,从 (A、B) 到 (c, d) 论符号 r )存在 a ->r c 是在 一 和 b ->r d 是在 乙 .
• (a,b) 启动状态是否处于 ANB 敌我识别 一 和 乙 开始状态是否在 一 和 乙 分别。
• (a,b) 接受状态是否处于 ANB 如果在各自的fa中,每个fa都是一个接受状态。

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

我只是做了一个快速搜索,这个问题是可以解决的(aka可以做),但我不知道有什么好的算法可以做到。一个是解决方案是:

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

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