你如何构建两个DFA的联合？

Question

有没有人对构建两个给定DFA的并集算法有直截了当的描述？例如,假设我们有两个DFA超过{0,1}

{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,或者通常你必须在union DFA中维护两个DFA的状态.

这就是为什么你必须为联合DFA创建新状态作为原始状态的直接乘法.这样,原始DFA中的每种状态组合都具有状态.

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

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