从正规式r构造NFAM 2.当r中含有k个运算符时，分下列三种情况 r=2r=12r=r*,对应的三个 状态转换图如下： 替换规则 2 2 2 qo q2 22 qo 02 28-二月-23 ☒6
28-二月-23 6 从正规式 r 构造NFA M 2.当 r 中含有 k 个运算符时，分下列三种情况 r = r1| r2 r = r1 r2 r = r1 * ，对应的三个 状态转换图如下： = 1 | 2 = 1 2 = 1 * 1 2 q0 q1 q2 1 q0 q1 q2 ε ε 2 1 q0 q1 替 换 规 则
从正规式r构造NFAM举例 已知正规式r=(ab)*(aabb)(ab)* 试给出能识别L(r)的确定有限自动机FA (a b)*(aa bb)(a b)* 〉 3 a a 28-二月-23 节目录 ☒7
28-二月-23 7 从正规式 r 构造NFA M 举例 已知正规式 r=(a|b)*(aa|bb)(a|b)* 试给出能识别L(r)的确定有限自动机NFA (a | b )*(aa | bb) (a | b )* X Y a X 5 b 3 a 4 2 b 1 a b 6 Y b a 节目录
3.4.3NFA的确定化p50 SDFA是NFA的特例： (1)NFA的初态集中只有唯一初态 (2)状态转换函数单值（状态集之间转换） S对每一个NFAN一定存在一个DFAM,使得 L M)=LN) 即对每个NFAN存在着与之等价的DFAM。 S注意：与某一NFA等价的DFA不唯一。 确定化 NFA- DFA 子集法 28-二月-23 ☒28
28-二月-23 8 3.4.3 NFA的确定化 p50 §DFA是NFA的特例： （1）NFA的初态集中只有唯一初态 （2）状态转换函数单值（状态集之间转换） §对每一个NFA N一定存在一个DFA M，使得 L(M)=L(N) 即对每个NFA N存在着与之等价的DFA M。 §注意：与某一NFA等价的DFA不唯一。 NFA DFA 确定化 子集法
I-状态集 Ia输入a到达的状态集 Ib输入b到达的状态集 子 {X,5,1} {5,3,1) {5,4,1} 5,3,1 5,2,3,1,6,Y} {5,4,1} 举 {5,4,1} {5,3,1 {5,2,4,1,6,Y} {5,2,3,1,6,Y} {5,2,3,6,1,Y} {5,4,6,1,Y} {5,2,4,1,6,Y {5,3,6,1,Y] {5,2,4,6,1,Y} {5,4,6,1,Y} {5,6,3,1,Y) {5,2,6,4,1,Y} {5,3,6,1,Y 5,2,6,3,1,Y) {5,6,4,1,Y 3 →区 28-二月-23 ☒9
28-二月-23 9 子 集 法 举 例 {X,5,1} I-状态集 Ia-输入a到达的状态集 Ib-输入b到达的状态集 {5,3,1} {5,4,1} {5,3,1} {5,4,1} {5,2,3,1,6,Y} {5,4,1} {5,2,3,1,6,Y} {5,3,1} {5,2,4,1,6,Y} {5,2,4,1,6,Y} {5,2,3,6,1,Y} {5,4,6,1,Y} {5,3,6,1,Y} {5,2,4,6,1,Y} {5,4,6,1,Y} {5,6,3,1,Y} {5,2,6,4,1,Y} {5,3,6,1,Y} {5,2,6,3,1,Y} {5,6,4,1,Y} a X 5 b 3 a 4 2 b 1 a b 6 Y b a
状态子集重命名后的 确定化后的 状态转换矩阵 状态转换图 a a b 0 1 2 5 1 3 2 2 1 4 3+ 3 5 4 6 4 5 6 4 6+ 3 5 28-二月-23 ☒10
28-二月-23 10 状态子集重命名后的 状态转换矩阵 确定化后的 状态转换图 a b 0 - 1 2 3 + 1 2 3 2 1 4 3 5 4 + 6 4 5 + 6 4 6 + 3 5 a 1 0 b 2 a b b 3 5 a b a a b 4 6 b a b a