Download presentation
Presentation is loading. Please wait.
1
第二章 词法分析3 非确定有限自动机NFA 非确定有限自动机（NFA）的定义 NFA的确定化：NFA到DFA的转换（子集法）
2
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
3
带“空”边的自动机 + D - - 1 2 2 ε D NFA 3
4
（一） 非确定有限自动机NFA的定义 一个非确定有限自动机NFA A是一个五元组A=(S,,f,S0,Z).其中 S：状态集 ：字母表
f: S(∪{})2S，f(si,a)={sj1,sj2,…} S0：初始状态集 Z：终止状态集
5
（二）NFA和DFA的区别 总结来看NFA与DFA相比其非确定性有3点：
状态转换函数可为多值函数，一个状态接受同一个输入字符可以转向多个不同后继状态下； 允许有多个开始状态； 允许有空边，即在没有任何输入的情况下允许进行状态转换。 之前的保研考试还考过这个
6
例：有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*
7
（三）NFA所能接受的语言 定义：设A是一个NFA，A= (S,, f, S0, Z),
则定义A接受（识别）的语言L(A)为从任意初始状态到任意终止状态所接受的字符串的集合。 NFA所能接受的串与DFA的定义是相同的， 但NFA实现起来很困难
8
（四） 自动机的等价和确定化 定义：设A1和A2是同一个字母表上的自动机，如果有L(A1)=L(A2)，则称A1和A2等价。
NFA的确定化 由NFA构造出与其等价的DFA称为NFA确定化。 8
9
就是让DFA的某一个状态去记录NFA读入一个输入符号后可能达到的一组状态。
NFA到DFA的确定化转换算法 NFA确定化子集法构造思想： 就是让DFA的某一个状态去记录NFA读入一个输入符号后可能达到的一组状态。 NFA A {sj1,sj2,…,sjn} DFA A’ si’ 9
10
无空边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
11
带“空”边的NFA自动机 + D - - 1 2 2 ε D D={1,2,…,9} 11
12
带空边的NFA的确定化 定义1：状态集J的闭包 设J是NFA A状态集的子集，定义J的闭包 -CLOSURE(J)状态集为：
① 若状态q ∈J，则q ∈_CLOSURE(J)； ② 若q ∈_CLOSURE(J)，那么从q出发经任意条ε边到达的任何状态q’都属于-CLOSURE(J)。 12
13
设I={S1, … , Sm }是NFA状态集的子集，对于任意的输入a，则状态集I经过输入a转换的状态集合
Ia=_CLOSURE(J) 其中: J = f (S1,a) f (S2,a)… f(Sm,a) 13
14
带空边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
15
例：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}*
16
输入字 状态 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}
17
（五） DFA的化简 DFA的化简的必要性 1 2 3 4 5 6 7 a b c d a b c d 1 2 3 4
18
最小自动机 最小自动机定义： 如果DFA M 没有无关状态，也没有等价状态，则称M为最小(最简)自动机。
（1）无关状态：从开始状态没有到S的通路，或S到任意终止状态无通路，称S为M的无关状态。 a 1 2 b 所以自动机最小化就是两个问题，一个是合并可以合并的等价状态，一个是删去无用的无关状态。如果一个自动机没有这两种状态，那他就是我们所说的最简自动机，我们想要化简自动机的话只需要把这两个工作都完成就可以了。 对于第二种类型来说是比较好处理的，看一个节点是否有通路其实一看就知道了，找到这类状态直接删掉。麻烦的是等价状态，哪些状态是可以合并的，哪些是不能的，有时候简单的可以看出来，但是任给你一个自动机，你想直接看出来是很难的，所以下面就要介绍怎么化简。 （2）等价状态：对DFA中的两个状态S1和S2，如果将它们看作是初始状态，所接受的符号串相同，则定义S1和S2是等价的。
19
（1）一致性条件：S1和S2同时为可接受状态或不可接受状态。 （2）蔓延性条件：S1和S2对所有输入符号必须都要转换到等价状态里。
两个状态等价的条件 两个状态S1和S2等价的条件是： （1）一致性条件：S1和S2同时为可接受状态或不可接受状态。 （2）蔓延性条件：S1和S2对所有输入符号必须都要转换到等价状态里。 所以自动机最小化就是两个问题，一个是合并可以合并的等价状态，一个是删去无用的无关状态。如果一个自动机没有这两种状态，那他就是我们所说的最简自动机，我们想要化简自动机的话只需要把这两个工作都完成就可以了。 对于第二种类型来说是比较好处理的，看一个节点是否有通路其实一看就知道了，找到这类状态直接删掉。麻烦的是等价状态，哪些状态是可以合并的，哪些是不能的，有时候简单的可以看出来，但是任给你一个自动机，你想直接看出来是很难的，所以下面就要介绍怎么化简。 DFA终止状态和非终止状态是不等价的。
20
DFA化简方法—状态分离法 状态分离法步骤 状态分离初始时：终止状态为一组，非终止状态为一组；
对每一组进行分离：若每组中的元素接收中的任意字符会映射到不同的组，则表示他们不等价，就可以分离出来建立新的组； 重复2，知道没有新组产生，此时每组中的状态都为等价状态。 20
21
例1 a 1 7 b 4 6 8 1:初始状态划分: 2 2 5 5 5 5 { 1，2，3，5 } ∪ { 4，6，7，8 }
2：经过a转向 说的话还是抽象，我们来看个例子 {1235} {4678} 先从终止分 ，一看 不能分 暂时 再看1235 1都1组 2a 到缺省 b到2组 所以不等的 变成了{1 3} {2 5}前面不能分离的现在可能也可能分离了，因为原来在一组 现在分成两组了 再做 然后发现都不能分离了，就分离结束了 { 1，2，3，5 } ∪ { 4，6，7，8 } 经过b转向
22
a 1 7 b 3 2 5 4 6 8 例1 3经过b转向 说的话还是抽象，我们来看个例子 {1235} {4678} 先从终止分 ，一看 不能分 暂时 再看1235 1都1组 2a 到缺省 b到2组 所以不等的 变成了{1 3} {2 5}前面不能分离的现在可能也可能分离了，因为原来在一组 现在分成两组了 再做 然后发现都不能分离了，就分离结束了 { 1，3} ∪ { 2，5 } ∪ { 4，6，7，8 } 3经过a转向
23
a 1,3 b 4,6,7,8 2,5 化简后 S0 S1 S2 3经过b转向 说的话还是抽象，我们来看个例子 {1235} {4678} 先从终止分 ，一看 不能分 暂时 再看1235 1都1组 2a 到缺省 b到2组 所以不等的 变成了{1 3} {2 5}前面不能分离的现在可能也可能分离了，因为原来在一组 现在分成两组了 再做 然后发现都不能分离了，就分离结束了 { 1，3} ∪ { 2，5 } ∪ { 4，6，7，8 } 3经过a转向
24
例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
25
A C D B E a b SS= {A,C}∪{B}∪{D}∪{E} = {A}∪{B}∪{D}∪{E} b A D B E a
26
（六）正则表达式和有限自动机的相互转化 定理 对∑上的每一个正则表达R，存在一个∑上的非确定有限自动机M，使得 L(M) = L(R) .
NFA 正则表达式 DFA
27
正则表达式到NFA的转换 W X W 1 2 3 a b 1 2 a b a | b b* 27
28
S Z A S Z S A B Z 例 ：有正规表达式(a|b)*aa,为之构造等价的NFA. (a|b)*aa (a|b)* (a|b)*
29
(a|b)* S A B a Z S C A B a Z ε a|b S C A B a Z ε a,b
30
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
31
例 有如下图所示的NFA M,试构造与之等价的正则表达式r
6 5 1 3 2 4 b
32
Z S a 6 5 1 3 2 4 b ε ba S ε a ab Z b 6 5 1 2
33
ba S ε a ab Z b 6 5 1 2 ab|ba 6 5 b Z ε S a 1 2
34
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
35
练习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 直观的看，肯定是这样的一种形式，那我们就看看用公式怎么做 写一下这个过程 这个自动机是非确定的，所以要进行转化，转换成确定的。给出这个过程
36
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}*
37
转化成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
38
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
39
S Z S A B Z 练习2 构造与正则表达式a((a|b)*ab*a)b等价的最简DFA，要求给出中间转换步骤和结果。
40
a S A B (a|b)*ab*a Z b S D C B a Z b A E (a|b)* b*
41
S A C B a Z b (a|b)*ab* S D C B a Z b A E (a|b)* b*
42
S C B a Z b A E D F ε a,b G ε b (a|b)* b*
43
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} *
44
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
45
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
46
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
47
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
48
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
Similar presentations
