两个自动机之间的等价
确定两个自动机之间的等价性的最佳或最简单的方法是什么？
即，如果给定两个有限自动机 A 和 B，我如何确定两者是否识别相同的语言？
它们都是确定性的或都是非确定性的。
Which is the best or easiest method for determining equivalence between two automata?
I.e., if given two finite automata A and B, how can I determine whether both recognize the same language?
They are both deterministic or both nondeterministic.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
一种不同的、更简单的方法是对自动机进行补充和交叉。自动机
A等价于B当且仅当L(A)包含在L(B)中，反之亦然这是当且仅当L(B)和L(A)的补集之间的交集为空，反之亦然。以下是检查
L(A)是否包含在L(B)中的算法：B。然后，使每个接受状态都拒绝，每个拒绝状态都接受。您将获得一个可识别L(B)补集的自动机。L(B)和L(A)的补集的交集的语言。即，为步骤 1 中的自动机和A的交集构造一个自动机。要使两个自动机U和V相交，您可以构造一个状态为U x V的自动机。自动机从状态(u,v)移动到(u',v')，且字母为a，前提是存在转换u --a-->和U中的 u'v --a-->。接受状态是状态V中的 v'(u,v)，其中u在U中接受，而v在 <代码>V。如果
L(A)包含在L(B)中，我们需要运行相同的算法来检查L(B)是否包含在L(A)。A different, simpler approach is to complement and intersect the automata. An automaton
Ais equivalent toBiffL(A)is contained inL(B)and vice versa which is iff the intersection between the complement ofL(B)andL(A)is empty and vice versa.Here is the algorithm for checking if
L(A)is contained inL(B):Busing the subset construction. Then, make every accepting state rejecting and every rejecting state accepting. You get an automaton that recognizes the complement ofL(B).L(B)andL(A). I.e., construct an automaton for the intersection of the automaton from step 1 andA. To intersect two automataUandVyou construct an automaton with the statesU x V. The automaton moves from state(u,v)to(u',v')with letteraiff there are transitionsu --a--> u'inUandv --a--> v'inV. The accepting states are states(u,v)whereuis accepting inUandvis accepting inV.If
L(A)is contained inL(B)we need to run the same algorithm to check ifL(B)is contained inL(A).如果两个非确定性有限自动机 (NFA) 接受相同的语言，那么它们是等价的。
为了确定它们是否接受相同的语言，我们会考虑每个 NFA 都有一个最小的 DFA，其中没有两个状态是相同的。最小的 DFA 也是独一无二的。因此，给定两个 NFA，如果发现它们对应的最小 DFA 是等价的，那么这两个 NFA 也一定是等价的。
要深入研究该主题，我强烈建议您阅读形式化简介语言和自动机。
Two nondeterministic finite automota (NFA's) are equivalent if they accept the same language.
To determine whether they accept the same language, we look at the fact that every NFA has a minimal DFA, where no two states are identical. A minimal DFA is also unique. Thus, given two NFA's, if you find that their corresponding minimal DFA's are equivalent, then the two NFA's must also be equivalent.
For an in-depth study on this topic, I highly recommend that you read An Introduction to Formal Language and Automata.
我只是改写 @Guy 的答案。
为了比较两者都接受的语言，我们必须弄清楚
L(A)是否等于L(B)。因此，您必须确定 L(A)-L(B) 和 L(B)-L(A) 是否为空集。 （原因 1）
第 1 部分：
为了找出这一点，我们从 NFA A 和 NFA B 构造 NFA X，%20%5Ccup%20(B%20%5Ccap%20A'))
。
如果 X 为空集，则
L(A) = L(B)，否则L(A) != L(B)。 （原因2）第二部分：
现在，我们必须找到一种有效的方法来证明或反驳
X是空集。当 DFA 或 NFA 时 X 何时为空？答案：当没有从X的起始状态到任何最终状态的路径时，X将为空。我们可以使用BFS或DFS来实现这一点。原因1：如果两者都设置为空，则
L(A) = L(B)。原因2：我们可以证明正则语言集合在交集和并集下是闭集。这样我们就能够高效地创建 NFA X。
对于集合：
)
I am just rephrasing answer by @Guy.
To compare languages accepted by both we have to figure out if
L(A) is equal to L(B)or not.Thus, you have to find out if
L(A)-L(B) and L(B)-L(A)is null set or not. (Reason1)Part1:
To find this out, we construct NFA X from NFA A and NFA B,%20%5Ccup%20(B%20%5Ccap%20A'))
.
If X is empty set then
L(A) = L(B)elseL(A) != L(B). (Reason2)Part2:
Now, we have to find out an efficient way of proving or disproving
X is empty set. When will be X empty as DFA or NFA? Answer: X will be empty when there is no path leading from starting state to any of the final state of X. We can use BFS or DFS for this.Reason1: If both are null set then
L(A) = L(B).Reason2: We can prove that set of regular languages is closed under intersection and union. Thus we will able to create NFA X efficiently.
and for sets:
)