10

有没有人对构造两个给定 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 案例，还是我遗漏了什么？

4

1 回答 1

13

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

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

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

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

于 2010-12-15T12:56:50.823 回答