你如何构建两个 DFA 的联合? [英] How do you construct the union of two DFA's?

问题描述

有没有人对构造两个给定 DFA 的并集的算法有一个简单的描述?例如，假设我们有两个超过 {0,1} 的 DFA，其中

Does anyone have a straightforward description of the algorithm for constructing the union of two given DFA's? For example, say we have two DFA's over {0,1} where

{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

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

I have a resulting transition table showing the union as:

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

我的讲义中有一个图片解决方案，但想看看其他人会如何描述它.由此，我可以看到我们本质上使用这两个原始表的状态值相乘"以产生更大的转换表.因此可以从结果表中得出 DFA.这听起来是否正确?这是否适用于所有 DFA 案例，还是我遗漏了什么?

I have a pictorial solution in my lecture notes, but would like to see how others would describe it. From this, I can see that we essentially "multiply" these two original tables using their state values to result in a larger transition table. The DFA can be thus drawn from the resultant table. Does this sound right and should this work for all DFA cases, or is there something I'm missing?

推荐答案

理解的关键是你必须同时运行两个 DFA，或者一般来说你必须在联合 DFA 中维护两个 DFA 的状态.

The key to understand is that you have to run the two DFAs simultanously, or in general you have to maintain the states of both DFAs in the union DFA.

这就是为什么您必须为联合 DFA 创建新状态作为原始状态的直接乘法.通过这种方式，您可以为原始 DFA 中的每个状态组合创建一个状态.

That's why you have to create the new states for the union DFA as a direct multiplication of the original states. This way you have a state for every combination of the states in original DFAs.

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

The transition rules for the new DFA can be directly calculated then. For example if you are in state Ab, and you get a 0 on input, the first DFA would go to state B and the second one to state b, so the union DFA's next state for this input will be Bb.

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

This method works in every case when you need to make a union of two or more DFAs. The resulting DFA may not be optimal, but later you can minimize it with any algorithm you like.

这篇关于你如何构建两个 DFA 的联合?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！