两个自动机之间的等价

Question

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

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

它们既具有确定性,也具有不确定性.

Answer 1

一种不同的,更简单的方法是补充和交叉自动机.自动机A等同于Biff L(A)包含在内L(B),反之亦然,如果L(B)和的互补之间的交集L(A)是空的,反之亦然.

以下是检查是否L(A)包含在以下内容的算法L(B):

1. 补充:首先,B使用子集构造确定.然后,让每个接受状态拒绝,每个拒绝状态接受.你得到一个识别补充的自动机L(B).
2. 路口:构造一个承认是互补的交集语言的自动机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.
3. 在步骤2中构造自动机之后,所需要的只是检查空虚.也就是说,自动机接受了一个词.这是最简单的部分 - 使用BFS算法在自动机中找到从初始状态到接受状态的路径.

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

Answer 2

如果它们接受相同的语言,则两个不确定的有限自动机(NFA)是等价的.

为了确定它们是否接受相同的语言,我们会看到每个NFA都具有最小DFA的事实,其中没有两个状态是相同的.最小的DFA也是独一无二的.因此,给定两个NFA,如果您发现它们相应的最小DFA是等效的,那么两个NFA也必须是等价的.

有关该主题的深入研究,我强烈建议您阅读"形式语言和自动机简介".