编译原理-DFA与NFA的等价性

原创
2020/03/15 20:44
阅读数 1.7K

DFA与NFA的等价性

DFA与NFA的等价性,使得L(M)=L(M’)

NFA 和DFA的差别

状态 NFA DFA
初始状态 不唯一 唯一
弧上的标记 字(单字符字、ε) 字符
转换关系 非确定 确定

DFA与NFA的等价性证明

假定NFA M=<S, Σ, δ, S 0 , F>,我们对M的状态转换图进行以下改造:

NFA

引进新的初态结点X和终态结点Y,X,Y∉S,从X到S 0中任意状态结点连一条ε箭弧, 从F中任意状态结点连一条ε箭弧到Y。(解决初始状态唯一性) DFA

对M的状态转换图进一步施行替换,其中k是新引入的状态。(简化弧上的标记)

然后下面是NFA转换前后的状态

总来时就是两步走,第一步加入唯一的初态,第二步就是引入中间节点,将弧上的标记拆分成单字符

DFA与NFA的等价性证明

  • NFA确定化--子集法(解决ε弧和转换关系)
  • 设I是的状态集的一个子集,定义I的ε-闭包ε-closure(I)为:
    • 若s∈I,则s∈ε-closure(I);
    • 若s∈I,则从s出发经过任意条ε弧而能到达的任何状态s’都属于ε-closure(I) 即,ε-closure(I)=I∪{s’|从某个s∈I出发经过任意条ε弧能到达s’}

设a是Σ中的一个字符,定义 I a = ε-closure(J) 其中,J为I中的某个状态出发经过一条a弧而到达的状态集合。

转换过程

确定化:不失一般性,设字母表只包含两个 a 和b,我们构造一张计算状态集的转换表:

  1. 首先,置第1行第1列为ε-closure({X})求出这一列的I a ,I b ;
  2. 然后,检查这两个I a ,I b ,看它们是否已在表中的第一列中出现,把未曾出现的填入后面的空行的第1列上,求出每行第2,3列上的集合...
  3. 重复上述过程,直到所有第2,3列子集全部出现在第一列为止

转换矩阵:

I Ia Ib
ε-closure({X})={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,5,4,2,Y} {1,3,5,2,4,Y} {1,6,4,2,Y}
{1,6,4,2,Y} {1,5,4,2,Y} {1,3,6,2,4,Y}
  1. 把表看成状态转换矩阵,子集视为状态
  2. 转换表唯一刻划了一个确定的有限自动机M
    1. 初态是ε-closure({X}) 2.. 终态是含有原终态Y的子集
  3. 不难看出,这个DFA M与M’等价
  4. 对于每个NFA M存在一个DFA M ’ ,使得 L(M)=L(M’)
  5. NFA和DFA等价

矩阵项化简

参考中国大学MOOC 国防科技大学 《编译原理》课程文档

展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部