finite-automata - 两个自动机之间的等价性

Question

哪个是确定两个自动机之间等价的最佳或最简单的方法？

即，如果给定两个有限自动机 A 和 B，我如何确定两者是否识别相同的语言？

它们都是确定性的或都是非确定性的。

Answer 1

一种不同的、更简单的方法是对自动机进行补充和交叉。一个自动机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 .

在步骤 2 中构建自动机后，所需要做的就是检查空性。即，是否有自动机接受的词。这是最简单的部分——使用 BFS 算法在自动机中找到从初始状态到接受状态的路径。

如 L(A)包含在 L(B) 中我们需要运行相同的算法来检查是否 L(B)包含在 L(A) 中.