union - 您如何构建两个DFA的并集？

Question

有人对构建两个给定DFA的并集的算法有一个简单的描述吗？例如，假设我们在{0,1}上有两个DFA，其中

{w|w has an odd number of characters}
  w has states A and B

delta | 0  | 1
----------------
  A   | B  | B
----------------
  B   | A  | A


{x|x has an even number of 1s}
  x has states a and b

delta | 0  | 1
----------------
  a   | a  | b
----------------
  b   | b  | a

我有一个结果转换表，该联合显示为:

delta | 0  | 1 
----------------
  Aa  | Ba | Bb
----------------
  Ab  | Bb | Ba
----------------
  Ba  | Aa | Ab
----------------
  Bb  | Ab | Aa

我的讲义中有一个图形化的解决方案，但我想看看其他人如何形容它。从中可以看出，我们实质上使用这两个原始表的状态值来“乘”这两个原始表，以生成更大的过渡表。因此可以从结果表中提取DFA。这听起来是否正确，应该适用于所有DFA案例，还是我缺少什么？

Answer 1

要理解的关键是，您必须同时运行两个DFA，或者通常必须在联合DFA中维护两个DFA的状态。

这就是为什么您必须为联合DFA创建新状态作为原始状态的直接乘法。这样，您就可以为原始DFA中的每个状态组合都拥有一个状态。

然后可以直接计算新DFA的转换规则。例如，如果您处于状态Ab，并且输入为0，则第一个DFA将进入状态B，第二个DFA将进入状态b，因此该输入的联合DFA的下一个状态将为Bb。

当您需要合并两个或更多DFA时，此方法适用于每种情况。产生的DFA可能不是最佳的，但是稍后您可以使用任何喜欢的算法将其最小化。