确定两个自动机之间等价的最好或最简单的方法是什么？
即，如果给定两个有限自动机 A 和 B，我如何确定两者是否识别相同的语言？
它们都是确定性的或都是非确定性的。
问问题
29084 次
3 回答
17
另一种更简单的方法是对自动机进行补充和相交。一个自动机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构造一个带有 states 的自动机U x V。如果in和in存在转换，则自动机从 state 移动(u,v)到(u',v')with letter 。接受状态是正在接受和正在接受的状态。au --a--> u'Uv --a--> v'V(u,v)uUvV - 在步骤 2 中构建自动机后，所需要做的就是检查空性。即，是否有自动机接受的词。这是最简单的部分——使用 BFS 算法在自动机中找到从初始状态到接受状态的路径。
如果L(A)包含在L(B)我们需要运行相同的算法来检查是否L(B)包含在L(A)。
于 2012-09-27T14:09:57.200 回答
12
如果两个非确定性有限自动机 (NFA) 接受相同的语言，则它们是等价的。
为了确定它们是否接受相同的语言，我们查看每个 NFA 都有一个最小 DFA 的事实，其中没有两个状态是相同的。最小 DFA 也是独一无二的。因此，给定两个 NFA，如果你发现它们对应的最小 DFA 是等价的，那么这两个 NFA 也一定是等价的。
对于这个主题的深入研究，我强烈推荐你阅读An Introduction to Formal Language and Automata。
于 2011-08-01T22:15:17.320 回答
1
我只是改写@Guy的回答。
要比较两者都接受的语言，我们必须弄清楚是否L(A) is equal to L(B)。
因此，您必须找出是否L(A)-L(B) and L(B)-L(A)设置为空。（原因 1）
第1部分：
为了解决这个问题，我们从 NFA A 和 NFA B 构建 NFA X，...
如果 X 为空集，则L(A) = L(B)else L(A) != L(B)。（原因 2）
第2部分：
现在，我们必须找到一种有效的证明或反证方法X is empty set。X 什么时候会为 DFA 或 NFA 为空？答：当没有从 X 的起始状态到任何最终状态的路径时，X 将为空。我们可以为此使用 BFS 或 DFS。
原因1：如果两者都设置为空，则L(A) = L(B)。
理由2：我们可以证明正则语言集在交集和并集下是封闭的。因此，我们将能够有效地创建 NFA X。
对于集合：
于 2017-02-11T12:51:16.127 回答