关于DFA交并的无用思考

$\mathcal{Author:CoolWind}$

本来是一篇很早就想写的计算理论学习笔记，在今天复习期中的时候终于想起来补档。

本文是关于如何优雅（也许）的写出DFA的交并的一篇文章，内容很简单，也许无用，仅供参考。

主要步骤

本文章主要一道典型作业题作为例子进行说明，题干如下。

$$\begin{aligned} &请画出识别以下语言的DFA：\\ &\{\omega | \omega 含有至少2个0，并且至多含有1个1\} \end{aligned}$$

0x01 找出两个子语言

一般而言，子语言很容易找出，会有明显的连接词对其进行连接，如“和”、“并且”、“或”等词。

对于例题而言，他所包含的两个语言如下。

$$\begin{aligned} &A=\{\omega | \omega含有至少2个0\}\\ &B=\{\omega|\omega至多含有1个1\} \end{aligned}$$

根据连接词可以很容易的判断出原语言为$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的交并。

最后，祝愿期中烤漆的各位在计算理论都能拿到好成绩。