如何构建两个 DFA 的并集？
有谁对构造两个给定 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 案例，还是我遗漏了什么？
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
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?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
理解的关键是您必须同时运行两个 DFA，或者通常您必须在联合 DFA 中维护两个 DFA 的状态。
这就是为什么您必须为联合 DFA 创建新状态作为原始状态的直接乘法。这样，您就可以为原始 DFA 中的每个状态组合提供一个状态。
然后可以直接计算新DFA的转移规则。例如，如果您处于状态 Ab，并且输入为 0，则第一个 DFA 将进入状态 B，第二个 DFA 将进入状态 b，因此该输入的并集 DFA 的下一个状态将是 Bb。
当您需要对两个或多个 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.
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.
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.
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.