计算理论导引（关于自动机求交集的一个笔记

计算理论导引（关于自动机求交集的一个笔记

记录一个思考了好久，但是因为我的逻辑不够紧密而导致一直在绕弯路的问题，当我最后验证出来的时候我真的要被自己笑死了hhh

首先是已知条件：
第一个是补集的构造：

第二个是交集的构造：

然后我就想验证一下嘛，就打算用课堂上的例子来试一试

课堂上是并集，我就想着改成交集

a.先画出L1的自动机，并且改写出L1补集的自动机

b.画出L2的自动机，并且改写出L2补集的自动机

c.然后把他们两个并起来

d.然后取个反

显然这多少有点不太对劲
然后仔细一想，在c.合并的时候起始点应该是终止点才对，因为它可以直接通过两个空到达终止点

c*.把他们两个并起来，并把那个起始点设置成终止点

d*.取反

这显然也是不对的，因为这样子的结果是把他们两个并起来了啊
然后就在想是不是因为是NFA的原因

d**.化成DFA


e.然后再取反

这里没有化成最简状态，但是显然满足了交集的要求

然后这么简单的问题我居然想了这么多个来来回回，就感觉好傻啊hhh