·在状态转换图中，从某一初态结点到某一终态结点序列称为“路”。 6 字母或数字 (可识别所有标识符) 2.有穷自动机 单值函数唯一 ·定义：(DFA)M:M=(k,∑，Es,z)P52 例1：M={0,12,3,a,b,￡0，{3}) f.f(0.a)=1,f(0,b)=2,f(l,a)=3,f(1,b)=2 f(2,a)=1,f(2,b)=3 f(3.a)=3 f(3.b)=3 其矩阵表示： 、符号 状态 a 6 0 1 其转换图： 或b a. 例如：串abb,首先f0,a1一f〔1，b)=2一f2,b)=3∴该串是可识别的单词 串ab首先f0,a)=1→f(1,b)=2,终态是3∴.不是单词
在状态转换图中，从某一初态结点到某一终态结点序列称为“路”。 例： 例： = （可识别所有标识符） 2.有穷自动机 单值函数唯一 定义：（DFA）M: M=(k,, f, s, z) P52. ▲ ▲ 例 1：MD =( {0,1,2,3}, {a,b}, f, 0, {3} ) f: f(0,a)=1, f(0,b)=2, f(1,a)=3, f(1,b)=2 f(2,a)=1, f(2,b)=3 f(3,a)=3 f(3,b)=3 其矩阵表示： a b 0 1 2 1 3 2 2 1 3 3 3 3 终态 其转换图： a a a 或 b a,b a b 例如：串 abb, 首先 f(0,a)=1 → f(1,b)=2 → f(2,b)=3 该串是可识别的单词 串 ab 首先 f(0,a)=1→ f(1,b)=2 终态是 3不是单词 0 1 3 a a a b 2 b 0 字 母 1 字母或数字 符号 状态 0 1 3 2 b b
上例可识别：(ab)*(aaibb)(ab) 例2：0→回a⑥ L(Mo)=(c.a.aa,aaa.) 0 ② L(Mo-{a开头的a,b符号串； o L(MoF{e,任意长度的a,b符号串) 3.不确定有穷自动机 非单值函数一个初态集 (M-5 例：S=0,1,23}=4a,b}S0=01Z=3y ff0,a=1,3}f0,b={2,3}f1,aFof1,bF{1,3} f2,a=2,3}f2,b}=p f(3a)=o f3.b)=o 其矩阵表示： 符号 状态 a 6 0 1,3}2,3} 1,3} 2,3}9 3 转换图： 4.非确定有限自动机的确定化(NFA→DFA)P55.1.∑闭包2.a低转换 DFA是NFA的特例，对每个(NFA)M一定存在一个(DFA)M,使得L(M=L(M)与 某一NFA等价的DFA不唯一
上例可识别：（ab）* (aabb) (ab)*a 例 2： a L(MD)={ε,a,aa,aaa,.} ② a a b L(MD)={a 开头的 a,b 符号串} a b L(MD)={ε,任意长度 的 a,b 符号串｝ 3.不确定有穷自动机 非单值函数 一个初态集 ●定义：（NFA)M: M=(k,∑ , .f, s, z), . ▲ ▲ 例：S={0,1,2,3} ∑={a,b} S0={0} Z={3} f: f(0,a)={1,3} f(0,b)={2,3} f(1,a)= φ f(1,b)={1,3} f(2,a)={2,3} f{2,b}= φ f(3,a)= φ f(3,b)= φ 其矩阵表示： 符号 a b 0 {1,3} {2,3} 1 φ {1,3} 2 {2,3} φ 3 φ φ 转换图： b a b a,b a a 4. 非确定有限自动机的确定化（NFA→DFA）P55. 1.∑ 闭包 2.a 低转换 DFA 是 NFA 的特例，对每个（NFA）M 一定存在一个（DFA）M', 使得 L(M)=L(M')与 某一 NFA 等价的 DFA 不唯一 0 1 0 1 0 状态 0 1 3 2 b
例P564.8 例L. 0 先判断此为NFA,再NFA一→DFA确定化（注意：各列所有状态集都在第一列中出 现：则状态全部求完，即不再增大) 符号 0 状态 ①S ②[B ②B] ③[B.Z @[S] DFA ©[B,Z B,Z] o[s] 0,1 例2： 0.1 B 1 NFA 符号 状态 0 1 [A] [A] ②[A,B] ②[A,B O[A] [A.B.C] [A,B,C] ④[A,CJ ③[，B,C] )同为终态：所有会有原来NFA终态 ④[A,C ④[A,C] [A,B.C] 的集合在DFA中均为终态 ·FA(自动机)FNFA+DFA 5.确定有穷自动机的简化（最小化） ·没有多余状态：从该自动机的开始状态出发，任何输入串也不能到达的那个状态。 一致性条件 ·状态中没有两个是互相等价的< 蔓延性条件 例P584.9
例 P56 4.8 0 例 1. 0 0 1 先判断此为 NFA,再 NFA→DFA 确定化（注意：各列所有状态集都在第一列中出 现；则状态全部求完，即不再增大） 符号 0 状态 0 1 0 [S] ②[B] φ 1 0 ②[B] [S] 1 DFA [B,Z] [B,Z] [S] 0,1 例 2： 0,1 1 1 NFA 符号 状态 0 1 [A] [A] ②[A,B] ②[A,B] [A] [A,B,C] [A,B,C] ④[A,C] [A,B,C] 同为终态 所有会有原来 NFA 终态 ④[A,C] ④[A,C] [A,B,C] 的集合在 DFA 中均为终态 ● FA(自动机)= NFA+DFA 5.确定有穷自动机的简化（最小化） ● 没有多余状态：从该自动机的开始状态出发，任何输入串也不能到达的那个状态。 一致性条件 ● 状态中没有两个是互相等价的 蔓延性条件 a 例 P58 4.9 例 1. a a b b a a b a b b S B Z [B,Z] 1 2 3 A B C 0 1 3 5 6 4 2 b a b
①DFA ②S=3,4,5,6}5={0,1,2} S,中的四个状态经过a,b到达状态仍在S中，不再划分 ④S,中三个状态经过a,不在一个集合，S,划分为S={1,Sm(0,2} ⑤Sz再经过a,b,不在个集合∴.Sa划分为5a={0l,5m={2} ⑥把S,中四个等价状态合并 a.b 3】 b (简化后) 例2 S=1.2:S2=13} 经过ab都到同一集合∴合并 (简化后) B A b@】 © s=cdegy seAbe S1经过aC,D.G到中， ∴Sm=C,D,GS={E S中经过b,S={D,G,S={C}合并D,G S,经过a,S={A,B,S={F Sa经过b,Sm=(Ah,Sae(Bl @ (简化后)
DFA ② S1 ={3,4,5,6} S2={0,1,2} S1中的四个状态经过 a,b 到达状态仍在 S1中，∴不再划分 ④S2中三个状态经过 a,不在一个集合，∴S2划分为 S21=｛1｝，S22=｛0，2｝ ⑤S22再经过 a,b,不在一个集合∴S22划分为 S221={0},S222={2} ⑥把 S1中四个等价状态合并 a a a,b b b a b (简化后) 例 2. a a a S1={1,2} S2={3} b b 经过 a,b 都到同一集合∴合并 a b a (简化后) 例 3. a a b b a b b b a b S1={C,D,E,G} S2={A,B,F} S1经过 a,C,D,G 到Ф，E a G ∴S11={C,D,G} S12={E} S11中经过 b,S111={D,G},S112={C} ∴合并 D,G S2经过 a,S21={A,B},S22={F} b a S21经过 b,S211={A},S212={B} a b a b a b b (简化后) 0 1 3 2 1 2 3 1 3 A B C D F E G A B D F C E
列4 ①NFA(两个初态，Q经过1到达Q,Z) ② 人、符号 0 1 状 A[Q.P] B[P] cQ,2] B[P] D[Z] cQ.Z B(P] E[Q.Z.P] D(Z] B[P] B[P] E[Q.Z,P] B[P] E[Q.Z.P] DFA @ ④S={,B}S,={C,D,E S,=(C,E}S=(D) Su=(A)Si=(B) 0 B (简化后)
例 4. 1 1 0,1 0 1 NFA(两个初态，Q 经过 1 到达 Q，Z) ② 符号 0 1 状态 A[Q,P] B[P] C[Q,Z] B[P] Ф D[Z] C[Q,Z] B[P] E[Q,Z,P] D[Z] B[P] B[P] E[Q,Z,P] B[P] E[Q,Z,P] 0 1 0 1 0,1 0 1 DFA 1 ④ S1={A,B} S2={C,D,E} S21={C,E} S22={D} S11={A} S12={B} ⑤ 0 1 0 1 0,1 1 (简化后) Q P Z A B C D E A B C D