【编译原理】NFA的确定化和最小化

创作时间:

作者:

@小白创作中心

【编译原理】NFA的确定化和最小化

引用

CSDN

https://m.blog.csdn.net/csq0327/article/details/140053995

刚刚考完期末不久，总结一下编译原理里的一个很重要的题型--NFA的确定化和最小化，相信也是很多同学比较头疼的内容，实际上掌握了方法并不难。

1.NFA确定化

首先我们先引入一个状态转移矩阵，记录的是
闭包、识别某种内容可以达到的状态，即：

I Ia Ib
初始状态经过a可以达到的所有状态集经过b可以达到的所有状态集

这个矩阵也是我们将NFA化为DFA的依据
操作思路：
(1)从初态X出发，求出X的
闭包，作为第一个初始状态
(2)对状态集合中每个状态分别求经过a,b可以得到的状态，记为Ja,Jb
(3)求解Ja,Jb的
闭包，填入Ia,Ib表格中
(4)把右侧出现过的新状态填入最左侧的表格，重复以上操作，直到所有状态全在最左侧出现过

★明确几点：
(1)最左侧的
闭包是从初态开始的，一旦右侧产生了新的状态，就要把它放到左侧，继续产生新的状态，直到所有状态均在左侧出现过一次即可
(2)求解Ia,Ib时是先求经过a,b转移得到的状态Ja,Jb，但这样的状态显然是不足够的，还需要包含
闭包，因为NFA中空值是有机会识别的，所有可能的状态是必须包含识别空值产生的状态的
(3)所有状态确定后，要记得对状态进行命名，一般可以是ABC...或者123...，再根据状态矩阵画出DFA
(4)DFA的终态确定：只要新的状态集里包含原来的NFA的终态，就认为是终态

例题验证：
求解下图NFA等价的DFA

先求解
-closure(X)={X,1,2}，先填入表格最左侧一列，作为初始状态
接着求解Ja,Jb：
-closure(X)中所有状态经过a,b后得到的新状态为：Ja={1,5},Jb={1,6}
再求解Ia,Ib，也就是把经过
可以得到的状态加进去，即Ia={1,2,5},Ib={1,2,6}，填入表格
把这两个新状态依次加入最左侧一列，也作为新初始状态，接着求新状态
重复以上，直到所有状态均在最左侧出现过，状态矩阵就画好了

状态矩阵：
I Ia Ib
{X,1,2} {1,5,2} {1,6,2}
{1,5,2} {1,3,5,2,4,Y} {1,6,2}
{1,6,2} {1,5,2} {1,3,6,2,4,Y}
{1,3,5,2,4,Y} {1,3,5,2,4,Y} {1,6,4,2,Y}
{1,3,6,2,4,Y} {1,5,4,2,Y} {1,3,6,2,4,Y}
{1,6,4,2,Y} {1,5,4,2,Y} {1,3,6,2,4,Y}
{1,5,4,2,Y} {1,3,5,2,4,Y} {1,6,4,2,Y}

原NFA的终态是Y,含有Y的状态均认为是新DFA的终态
对状态依次命名，画出DFA可有：

2.DFA最小化

将NFA化为DFA后，仍然可能存在性质相同的状态，这样的状态对于状态转移贡献是等效的，可以合并，也就是进一步化为最简。
其实对DFA进行最小化很简单，可以先从定义角度出发：两个状态等价可以理解为两个状态识别任意相同字符可以停止于同一状态，就可以认为两个状态等价。因此最小化我们完全可以从定义入手，先将状态分为终态集和非终态集合，然后先对终态集合每个状态进行状态转移检测，如果转移结果相同，说明状态等价，可以合并为一个状态；完成终态的合并后，再依次对非终态集合的状态进行检测，方法一致，等价的就合为一个状态。

如上一道例题，对DFA最小化：
最小化DFA为：