如何获得DFA交集？

我们如何将两个dfa结合使用相交法？如何获得DFA交集？

2010-06-22 iva123

这功课吗？否则，我并不熟悉书中阐述的确切过程，但我敢打赌，我可以想出一个程序来组合两个在时间O（状态转换）中运行的DFA。 – Omnifarious 2010-06-22 19:41:36

我问了一个[类似的问题]（http://stackoverflow.com/questions/7732815/calculate-if-two-infinite-regex-solution-sets-dont-intersect）谁是[答案]（http：// stackoverflow。 com/a/7732923/188044）可能适用于这个问题。 – 2011-12-29 19:41:44

具体来说，EDIT之后的部分：说明如何让DFA接受L1与L2相交，给予DFA接受L1和L2。 – Patrick87 2012-02-04 13:59:40

使用叉积结构，正式解释here。

本质上，你跨产品在每一个状态的集合，以获得与每个机器的状态的任何组合相对应的元状态列表。这允许您进行并行评估以接受两者都接受。

来源

2013-06-11 23:37:33 akroy

如何获得DFA交集？

回答

相关问题