如何构建两个 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 可能不是最优的，但稍后您可以使用您喜欢的任何算法将其最小化。