关于DFA交并的无用思考
本文最后更新于:2023年10月25日 晚上
关于DFA交并的无用思考
$\mathcal{Author:CoolWind}$
本来是一篇很早就想写的计算理论学习笔记,在今天复习期中的时候终于想起来补档。
本文是关于如何
优雅(也许)的写出DFA的交并的一篇文章,内容很简单,也许无用,仅供参考。
主要步骤
本文章主要一道典型作业题作为例子进行说明,题干如下。
0x01 找出两个子语言
一般而言,子语言很容易找出,会有明显的连接词对其进行连接,如“和”、“并且”、“或”等词。
对于例题而言,他所包含的两个语言如下。
根据连接词可以很容易的判断出原语言为$A\cap B$。
0x02 画出识别两个子语言的DFA
根据DFA的构造原理可以很容易的构造出识别这两个子语言的DFA,图如下。
0x03 从初始状态开始,遍历两个自动机,构造组合自动机
这一步的意思是,两个自动机都从起始状态q0
开始进行遍历,即在每一个状态都考虑一下识别0
和识别1
时候下一步的状态,即如下图。
它的构造原理是,从上面两个子语言的自动机的起始状态(即组合自动机的q00
状态)开始,对每一个状态都考虑识别0
和1
的情况,并且将其经过转移之后的状态通过二维坐标表示。
例如:当状态为q00
时,如果识别了0
,那么根据子语言$A$的自动机可以知道,它的状态将从q0
转移到q1
;同理,根据子语言$B$的自动机可以知道,它的状态将仍保持q0
不变,因此在组合自动机中,状态由q00
转化为了q10
。
注意,在写出下一个状态的时候,记得检查一下转移后的状态是否已经存在了哦~如果存在的话就只需要指向该状态即可。
0x04 确定接收状态
在上一步中我们可以发现构造出来的自动机缺少接受状态。因此我们要确定接受状态。
根据语言交并的性质我们可以推出以下结论:
- 当所要构造自动机为两个自动机的交集,那么接受状态为两个子自动机同时达到接受状态时的状态,在例子中,接受状态即为
q20
、q21
两个状态。 - 当所要构造自动机为两个自动机的交集,那么接受状态为两个子自动机至少有一个达到接受状态时的状态,若以例子中的两个子语言为例进行语言的交,接受状态即为
q20
、q21
、q22
、q00
、q10
、q01
、q11
七个状态。
故可以得到上图自动机的接受状态。
0x05 冗余状态的合并
其实文章到上一步就可以结束了,但是由于有一些状态是可以合并的,因此可以将某些状态进行合并,但是这里并不对其进行解释,因为我认为不删减也不算错。
其实是作者能力较弱无法确定自己的方法是否正确,就不在这里写出。
如上图中的q02
、q12
、q22
状态均为无法接受的“边界状态”(我编的),并且三者存在可以转化的关系,因此可以合并成同一个,即如下图。
所以根据以上步骤也许就可以优雅的构造出来两个DFA的交并。
最后,祝愿期中烤漆的各位在计算理论都能拿到好成绩。