第二章 词法分析3 非确定有限自动机NFA 非确定有限自动机（NFA）的定义 NFA的确定化：NFA到DFA的转换（子集法）

2.5 非确定有限自动机NFA 例：设计一个DFA M， ={0,1}： L(M) ={x|x为01串结尾的字符串} S0 S1 S2 S0 S1 1 S2 1 NFA M’ 0,1 S0 S2 S1 1 2

带“空”边的自动机 + D - - 1 2 2 ε D NFA 3

（一） 非确定有限自动机NFA的定义 一个非确定有限自动机NFA A是一个五元组A=(S,,f,S0,Z).其中 S：状态集 ：字母表 f: S(∪{})2S，f(si,a)={sj1,sj2,…} S0：初始状态集 Z：终止状态集

（二）NFA和DFA的区别 总结来看NFA与DFA相比其非确定性有3点： 状态转换函数可为多值函数，一个状态接受同一个输入字符可以转向多个不同后继状态下； 允许有多个开始状态； 允许有空边，即在没有任何输入的情况下允许进行状态转换。 之前的保研考试还考过这个

例：有NFA A = （{s0,s1,s2}，{a, b}, f, {s0,s1}, {s2}） f(s0,a)={s0,s1} f(s0,b)={s0} f(s1, )={s2} f(s2,a)={s2} f(s2,b)={s2} a b  s0+ {s0,s1} {s0} s1+ {s2} s2*

（三）NFA所能接受的语言 定义：设A是一个NFA，A= (S,, f, S0, Z), 则定义A接受（识别）的语言L(A)为从任意初始状态到任意终止状态所接受的字符串的集合。 NFA所能接受的串与DFA的定义是相同的， 但NFA实现起来很困难

（四） 自动机的等价和确定化 定义：设A1和A2是同一个字母表上的自动机，如果有L(A1)=L(A2)，则称A1和A2等价。 NFA的确定化 由NFA构造出与其等价的DFA称为NFA确定化。 8

就是让DFA的某一个状态去记录NFA读入一个输入符号后可能达到的一组状态。 NFA到DFA的确定化转换算法 NFA确定化子集法构造思想： 就是让DFA的某一个状态去记录NFA读入一个输入符号后可能达到的一组状态。 NFA A {sj1,sj2,…,sjn} DFA A’ si’ 9

无空边NFA转换为DFA—子集法 NFA A:={a,b} S2 a S3 S0 a a Si Sm S4 a … … Sk b Sj a b S1 S5 Sn b Sl b b S6 S7 DFA A’ S1’ {S2 S3 S4 } a Sj’ {Sm Sn } a Sk’ {Sk Sl } b S0’ {S0 S1 } Si’ {Si Sj } … … S2’ {S5 S6 S7 } b

带“空”边的NFA自动机 + D - - 1 2 2 ε D D={1,2,…,9} 11

带空边的NFA的确定化 定义1：状态集J的闭包 设J是NFA A状态集的子集，定义J的闭包 -CLOSURE(J)状态集为： ① 若状态q ∈J，则q ∈_CLOSURE(J)； ② 若q ∈_CLOSURE(J)，那么从q出发经任意条ε边到达的任何状态q’都属于-CLOSURE(J)。 12

设I={S1, … , Sm }是NFA状态集的子集，对于任意的输入a，则状态集I经过输入a转换的状态集合 Ia=_CLOSURE(J) 其中: J = f (S1,a)  f (S2,a)… f(Sm,a) 13

带空边NFA转换为DFA—子集法 NFA：A ={a,b} a S5 S8 ε ε ε S0 a S6 … … S3 S2 ε S9 ε 状态集Ia={S5,S6 ,S7,S8,S9} a S5 S8 状态集I={S0,S1 ,S2,S3,S4} ε ε ε S0 a S6 … … S3 S2 ε S9 ε a S7 S4 S1 状态集J={S5,S6,S7} 状态集K={S0,S1} DFA：A’ S0’ I S1’ Ia a

例：NFA确定化 DFA a b S1+ S2* S3 S4* S5* {1,2}+ {4,5,7,6,2} {3,8} {4,5,7,6,2}* {3,9,8} S3 {3,8} {9} S4* {3,9,8}* {9} S5* 15 {9}*

输入字 状态 a b + 1 {4,5,7,6,2} 2 {1,2} {3,8} 3 * {4,5,7,6,2} 2 {9,3,8} 4 3 {3,8} {9} 5 * {9,3,8} 4 {9} 5 1 3 2 4 5 b a 5 * {9}

（五） DFA的化简 DFA的化简的必要性 1 2 3 4 5 6 7 a b c d a b c d 1 2 3 4

最小自动机 最小自动机定义： 如果DFA M 没有无关状态，也没有等价状态，则称M为最小(最简)自动机。 （1）无关状态：从开始状态没有到S的通路，或S到任意终止状态无通路，称S为M的无关状态。 a 1 2 b 所以自动机最小化就是两个问题，一个是合并可以合并的等价状态，一个是删去无用的无关状态。如果一个自动机没有这两种状态，那他就是我们所说的最简自动机，我们想要化简自动机的话只需要把这两个工作都完成就可以了。 对于第二种类型来说是比较好处理的，看一个节点是否有通路其实一看就知道了，找到这类状态直接删掉。麻烦的是等价状态，哪些状态是可以合并的，哪些是不能的，有时候简单的可以看出来，但是任给你一个自动机，你想直接看出来是很难的，所以下面就要介绍怎么化简。 （2）等价状态：对DFA中的两个状态S1和S2，如果将它们看作是初始状态，所接受的符号串相同，则定义S1和S2是等价的。

（1）一致性条件：S1和S2同时为可接受状态或不可接受状态。 （2）蔓延性条件：S1和S2对所有输入符号必须都要转换到等价状态里。 两个状态等价的条件 两个状态S1和S2等价的条件是： （1）一致性条件：S1和S2同时为可接受状态或不可接受状态。 （2）蔓延性条件：S1和S2对所有输入符号必须都要转换到等价状态里。 所以自动机最小化就是两个问题，一个是合并可以合并的等价状态，一个是删去无用的无关状态。如果一个自动机没有这两种状态，那他就是我们所说的最简自动机，我们想要化简自动机的话只需要把这两个工作都完成就可以了。 对于第二种类型来说是比较好处理的，看一个节点是否有通路其实一看就知道了，找到这类状态直接删掉。麻烦的是等价状态，哪些状态是可以合并的，哪些是不能的，有时候简单的可以看出来，但是任给你一个自动机，你想直接看出来是很难的，所以下面就要介绍怎么化简。 DFA终止状态和非终止状态是不等价的。

DFA化简方法—状态分离法 状态分离法步骤 状态分离初始时：终止状态为一组，非终止状态为一组； 对每一组进行分离：若每组中的元素接收中的任意字符会映射到不同的组，则表示他们不等价，就可以分离出来建立新的组； 重复2，知道没有新组产生，此时每组中的状态都为等价状态。 20

例1 a 1 7 b 4 6 8 1:初始状态划分: 2 2 5 5 5 5 { 1，2，3，5 } ∪ { 4，6，7，8 } 2 2 5 5 5 5 2：经过a转向 说的话还是抽象，我们来看个例子 {1235} {4678} 先从终止分 ，一看 不能分 暂时 再看1235 1都1组 2a 到缺省 b到2组 所以不等的 变成了{1 3} {2 5}前面不能分离的现在可能也可能分离了，因为原来在一组 现在分成两组了 再做 然后发现都不能分离了，就分离结束了 { 1，2，3，5 } ∪ { 4，6，7，8 } 经过b转向 3 4 3 7 6 6 8 8

a 1 7 b 3 2 5 4 6 8 例1 3 3 4 7 6 6 8 8 3经过b转向 说的话还是抽象，我们来看个例子 {1235} {4678} 先从终止分 ，一看 不能分 暂时 再看1235 1都1组 2a 到缺省 b到2组 所以不等的 变成了{1 3} {2 5}前面不能分离的现在可能也可能分离了，因为原来在一组 现在分成两组了 再做 然后发现都不能分离了，就分离结束了 { 1，3} ∪ { 2，5 } ∪ { 4，6，7，8 } 3经过a转向 2 2 5 5 5 5

a 1,3 b 4,6,7,8 2,5 化简后 S0 S1 S2 3 3 4 7 6 6 8 8 3经过b转向 说的话还是抽象，我们来看个例子 {1235} {4678} 先从终止分 ，一看 不能分 暂时 再看1235 1都1组 2a 到缺省 b到2组 所以不等的 变成了{1 3} {2 5}前面不能分离的现在可能也可能分离了，因为原来在一组 现在分成两组了 再做 然后发现都不能分离了，就分离结束了 { 1，3} ∪ { 2，5 } ∪ { 4，6，7，8 } 3经过a转向 2 2 5 5 5 5

例2： A C D B a b E STEP1.求初始划分: SS={A,B,C,D}∪{E} D C B A E {A,B,C}对a是否是可区分的？ {A,B,C}对b是否是可区分的？ D C B A E D C B A {A,B,C,D}对a是否是可区分的？ E {A, C}对a是否是可区分的？ D C B A E {A, C}对b是否是可区分的？ D C B A D C B A E {A,B,C,D}对b是否是可区分的？ STEP1.求初始划分: SS={A,B,C,D}∪{E} STEP2. {A,B,C,D} 是否是可区分的？ SS={A,B,C,D}∪{E} ={A,B,C}∪{D}∪{E} {A,B,C} 是否是可区分的？ SS={A,B,C,D}∪{E} ={A,B,C}∪{D}∪{E} ={A,C}∪{B}∪{D}∪{E} {A, C} 是否是可区分的？ E

A C D B E a b SS= {A,C}∪{B}∪{D}∪{E} = {A}∪{B}∪{D}∪{E} b A D B E a

（六）正则表达式和有限自动机的相互转化 定理 对∑上的每一个正则表达R，存在一个∑上的非确定有限自动机M，使得 L(M) = L(R) . NFA 正则表达式 DFA

正则表达式到NFA的转换  W X W 1 2 3 a b  1 2 a b a | b b* 27

S Z A S Z S A B Z 例 ：有正规表达式(a|b)*aa,为之构造等价的NFA. (a|b)*aa (a|b)* (a|b)*

(a|b)* S A B a Z S C A B a Z ε a|b S C A B a Z ε a,b

NFA到正则表达式的转换 W S02 Z01 Z02 … S02 Z01 Z02 … ε ε ε ε a b a b a a | b b b 3 1 3 a a | b 1 2 1 2 b b a b* c a c 1 3 1 2 3 30

例 有如下图所示的NFA M,试构造与之等价的正则表达式r 6 5 1 3 2 4 b

Z S a 6 5 1 3 2 4 b ε ba S ε a ab Z b 6 5 1 2

ba S ε a ab Z b 6 5 1 2 ab|ba 6 5 b Z ε S a 1 2

ab|ba 6 5 b Z ε S a 1 2 a 6 1 2 (ab|ba )a*b S ε Z a(ab|ba )a*b S Z

练习1： 给出一个正则表达式(a|b)(c|d)*(e|f)，请画出最简DFA。 (1)将正则表达式转为NFA e|f 3 1 a|b 2 e|f 3 1 a|b 2 (c|d)* a 2 4 b ε c d 1 3 e f 直观的看，肯定是这样的一种形式，那我们就看看用公式怎么做 写一下这个过程 这个自动机是非确定的，所以要进行转化，转换成确定的。给出这个过程

a 2 4 b ε c d 1 e f 转化成DFA (2) NFA的确定化 a b c d e f S0+ {0}+ {123} a 2 4 b ε c d 1 3 e f 转化成DFA a b c d e f S0+ {0}+ {123} {123} 画出来~ S1 {123} {23} {23} {4} {4} S2 {23} {23} {23} {4} {4} S3* {4}*

转化成DFA 2 3 c, d c ,d 1 a, b e, f a b c d e f S0+ S1 S2 S3 S3* 画出来~ 2 3 c, d c ,d 1 a, b e, f

3 a, b c ,d e, f 初始划分：{S0,S1,S2} {S3} 等价状态：{S0} {S1,S2} {S3} (3) DFA的最小化 a b c d e f S0+ S1 S2 S3 S3* 画出来~ (a|b)(c|d)*(e|f) 1,2 3 a, b c ,d e, f

S Z S A B Z 练习2 构造与正则表达式a((a|b)*ab*a)b等价的最简DFA，要求给出中间转换步骤和结果。

a S A B (a|b)*ab*a Z b S D C B a Z b A E (a|b)* b*

S A C B a Z b (a|b)*ab* S D C B a Z b A E (a|b)* b*

S C B a Z b A E D F ε a,b G ε b (a|b)* b*

F S C B Z A E D G ε a b a,b a b {S}+ {A,F,D} {A,F,D} {F,E,D,G,C} {F,D} {F,E,B,D,G,C} {F,G,D,C} {F,D} {F,E,D,G,C} {F,D} {F,E,B,D,G,C} {F,E,B,D,G,C} {F,G,Z,D,C} {F,G,D,C} {F,E,B,D,G,C} {F,G,D,C} {F,G,Z,D,C} {F,E,B,D,G,C} {F,G,D,C} *

a b 确 定 化 结 果 a b b a a b a a a b a b b 0+ 1 1 2 3 2 4 5 3 2 3 4 4 6 5 * a b 4 3 b a a b a a a 6 1 2 b a b 5 b

a b 划分法化简 a b b a a b a a a b a b b 0+ 1 1 2 3 2 4 5 3 2 3 4 4 6 5 4 5 * a b 4 3 b a a b a a a 6 1 2 b a b 5 b

a b 划分法化简 a b b a a b a a a b a b b 0+ 1 1 2 3 2 4 5 3 2 3 4 4 6 5 4 5 * a b 4 3 b a a b a a a 6 1 2 b a b 5 b

a b 划分法化简 a b b a a b a a a b a b b 0+ 1 1 2 3 2 4 5 3 2 3 4 4 6 5 4 5 * a b 4 3 b a a b a a a 6 1 2 b a b 5 b

a b 0+ 1 1 2 3 化简 结 果 2 4 5 3 2 3 4 4 6 5 4 5 6 4 5 * 1,3 2,5 a 4 6 b