当前位置 博文首页 > kbtx的博客:编译原理-第二章-词法分析之NFA、DFA之间的转化和DF
假定有如下图所示的非确定状态机(NFA) M = <S, ∑, δ, S0, F>
符号 | 含义 |
---|---|
S | 状态集合 |
∑ | 字母表 |
δ | 转换关系 |
S0 | 初始状态集 |
F | 终止状态集 |
我们对M的状态转换图进行以下改造:
如果每条弧只标记为∑上的一个字符或ε,我们就把这个NFA记为M’ 。
显然 L(M’)=L(M)
目的:解决ε弧和转换关系
例:对于如下NFA,假定 I = ε-closure({1}),求出I和Ia
解:I = ε-closure({1}) = {1,2}
假定J为I中的某个状态出发经过一条a弧而到达的状态集合,那么 J = {5,4,3}。其中,状态1经过a弧到达状态5,4,状态2经过a弧到达状态3。
于是,Ia = ε-closure(J) = ε-closure({5,4,3}) = {5,6,2,4,7,3,8}。
闭包传递关系如下:
<ε-closure id="J">
<state id="5">
<state id="6">
<state id="2"/>
</state>
</state>
<state id="4">
<state id="7"/>
</state>
<state id="3">
<state id="8"/>
</state>
</ε-closure>
不失一般性,设字母表只包含两个 a 和b,我们构造一张计算状态集的转换表:
为方便查找,我们将状态转换关系列表如下:
S\∑ | a | b | ε |
---|---|---|---|
Χ | 1,2 | ||
1 | 1 | 1 | 2 |
2 | 5 | 6 | |
3 | 4,Υ | ||
4 | 4 | 4 | Υ |
5 | 3 | ||
6 | 3 | ||
Υ |
I | Ia | Ib |
---|---|---|
ε-closure({X}) ={X,1,2} | J={1,5} Ia=ε-closure(J)={1,5,2} | {1,6,2} |
{1,5,2} | {1,2,5,3,4,Y} | |
{1,6,2} | {1,2,6,3,4,Y} | |
{1,2,5,3,4,Y} | {1,6,4,2,Y} | |
{1,2,6,3,4,Y} | {1,5,4,2,Y} | |
{1,6,4,2,Y} | ||
{1,5,4,2,Y} |
此时不再有新状态出现,计算完毕。
I | Ia | Ib |
---|---|---|
0 | 1 | 2 |
1 | 3 | 2 |
2 | 1 | 4 |
3 | 3 | 5 |
4 | 6 | 4 |
5 | 6 | 4 |
6 | 3 | 5 |
显然,NFA和DFA等价
目标:对于给定的DFA M,寻找一个状态数比M少的DFA M’,使得L(M)=L(M’)
把M的状态集划分为一些不相交的子集,使得任何两个不同子集的状态是可区别的,而同一子集的任何两个状态是等价的。
最后,让每个子集选出一个代表,同时消去其他状态。
例:按照上述原则对DFA的状态集合S进行第一次划分,正确的分法是将S分为终态和非终态
说明:终态读出ε后依然停留在终态,非终态读出ε后依然在非终态。
对于上图是我们从NFA转换得到的DFA,我们对其状态做出化简:
补充:根据上例的操作,我们可以通过列表大大简化化简步骤,如图:
蓝色字表示现行划分内的一个状态机识别某个字符后仍在这个划分内,红色字代表跳出了这个划分,具体跳入了哪个划分可以根据底色确定(这两个都跳入了灰色的划分)
检查状态机所在行的跳入情况,只有底色完全一致(考虑顺序)的({0}、{1}、{2}、{3,4,5,6})才属于同一个新的现行划分,并据此重新给不同状态机上色。
如果重新上色后同一划分内底色仍然一致,结束,否则继续划分,并再次上色。
(新划分内每一划分底色一致)
最后,根据底色的分布情况可以重新画出简化的DFA
请点击小标题观看视频
cs