DFA的化简 1. DFA的化简 所谓一个DFA M 的化简是指寻找一个状态数比 M 少的 DFA M' ，使得 L(M)=L(M')

Presentation on theme: "DFA的化简 1. DFA的化简 所谓一个DFA M 的化简是指寻找一个状态数比 M 少的 DFA M' ，使得 L(M)=L(M')"— Presentation transcript:

1 DFA的化简 1. DFA的化简 所谓一个DFA M 的化简是指寻找一个状态数比 M 少的 DFA M' ，使得 L(M)=L(M') 化简了的DFA满足两个条件: (1) 没有多余状态 (2) 它的状态集中没有两个状态是 互相等价的

2 DFA的化简 2. 多余状态 所谓有穷自动机的多余状态是指从该自动机的开始状态出发，任何输入串也不能到达的状态

3 DFA的化简 3.等价状态 设 DFA M＝(Q,Σ,f, S0, F), s, t∈ Q ，若对任何  *, f (s , )∈F 当且仅当 f (t , )∈F ，则称状态 s 和 t 是等价的。 如果 s 和 t 不等价, 则称 s 和 t 是可区别的 例如，终态与非终态是可区别的。因为终态有一条到达自身的ε道路，而非终态没有到达终态的ε道路

4 设 DFA M＝(Q,Σ,f, S0, F), 1, 2∈ Q ，若对任何  *, f (1 , )∈F 当且仅当
1 l 2 l d 1 设 DFA M＝(Q,Σ,f, S0, F), 1, 2∈ Q ，若对任何  *, f (1 , )∈F 当且仅当 f (2 , )∈F ，则称状态 s 和 t 是等价的。 譬如取为llld,ddll,lll,dd,ld,dl。 f (1 , ‘llld’)= f (2 , ‘llld’)=2 f (1 , ‘ddll’)= f (2 , ‘ddll’)=2 状态 1 和 2 是等价

5 3.4.5 DFA的化简 4.两个状态等价的条件: 5.化简方法 一致性条件: 状态s和t必须同时为 终态或非终态
输入：一个DFA M 输出：接受与M相同语言的DFA M '， 且其状态数最少

6 DFA的化简 化简方法: 无多余状态下把M的状态集 Q 分划成一些不相交的子集，使得每个子集中任何两个状态是等价的，而任何两个属于不同子集的状态都是可区别的 然后在每个子集中任取一个状态作“代表”, 而删去子集中其余状态, 并把射向其余状态的箭弧都改作射向作“代表”的状态

7 {A,F,G} {W,Z} {E,H,K} {I,L,M} {O,R,T,X}

8 A W H M T

9 3.4.5 DFA的化简 下面给出化简算法的具体执行步骤: 1. 将DFA M的状态集Q分成两个子集：终态集F和非终态集¬F，形成初始分划∏
2. 对∏使用如下方法建立新分划∏NEW： 对∏的每个状态子集G: (1) 把G分划成新的子集，使得G的两个状态s和t属于同一子集，当且仅当对任何输入符号a ，状态s和t转换到的状态都属于∏的同一子集

10 3.4.5 DFA的化简 用G分划出的所有新子集替换G, 形 成新的分划∏NEW； 如果∏NEW＝∏，则执行第4步；否则令
分划结束后，对分划中的每个状态子集，选出一个状态作代表，而删去其它一切等价的状态，并把射向其它状态的箭弧改为射向这个作为代表的状态

11 A B C D E a b D B A b a 例1. 将右面的DFA最小化 分析 由图可知，给定的DFA中无多余状态。
{A,B,C,D}a={B} {A,B,C,D}b={C,D,E} ∏=({A,B,C}{D}{E}) {A,B,C}a={B} {A,B,C}b={C,D} E D B A a b ∏=({A,C}{B}{D}{E}) {A,C}a={B} {A,C}b={C} ∏=({A,C}{B}{D}{E})

12 3.4.5 DFA的化简 例2. 将右面的DFA M最小化 分析 由图可知，给定的DFA无多余状态。 1 2
2 l d 1 分析 由图可知，给定的DFA无多余状态。 初始分划∏=({1,2}{0}) d 2 l {1,2}l ={2} {1,2}d ={2} d 1 l ∏=({1,2}{0})

13 有穷自动机到正规式的转换 1. 在 M 的转换图上添加两个结点： X 结和Y结。从X结用ε连线连结到M的所有初态结点，从 M 的所有终态结点用ε连线连结到 Y 结，从而构成一新的非确定有穷自动机 M’，它只有一个初态结 X和一个终态结Y。显然，L(M)=L(M’)。即，这两个NFA是等价的。

14 3.4.6 有穷自动机到正规式的转换 2. 逐步消去M’中的其它结点，直至只剩下X，Y结点。在消除结点过程中，逐步用正规式来标记相应的箭弧
有穷自动机到正规式的转换 2. 逐步消去M’中的其它结点，直至只剩下X，Y结点。在消除结点过程中，逐步用正规式来标记相应的箭弧 消除结点的过程是很直观的，只需反复使用下图的替换规则即可

15 3.4.6 有穷自动机到正规式的转换 A C B A B A B A B A C B A B r1 r2 r1r2 r1 r2 r1| r2
有穷自动机到正规式的转换 A C B r1 r2 A B r1r2 对于 代换为 A B r1 r2 A B r1| r2 对于 代换为 A C B r1 r3 r2 A B r1r2*r3 对于 代换为

16 有穷自动机到正规式的转换 例1. 设有穷自动机的状态图如图所示 试求该自动机识别语言的正规式 R=(10|01)(10|01)*

17 3.5 正规文法与有穷自动机 前面提到程序设计语言的单词符号可用乔母斯基3型文法——正规文法来描述
对于正规文法所描述的语言可用一种有穷自动机来识别 下面分别就右线性正规文法给出构造相应有穷自动机的方法

18 3.5 正规文法与有穷自动机 右线性正规文法到有穷自动机的转换方法 A→aB A→a 设给定了一个右线性正规文法
G = (VN ,VT , P , S) a= ε A→B 令f (A , ε)=B 则相应的有穷自动机 M = (Q , Σ , f , q0 , Z ) 1. 令 Q= VN∪{D} (D VN) Z={D} Σ = VT q0=S ∈ / 2. 对G中每一形如 A→aB (A ,B∈VN ,a∈VT∪{ε}) 的产生式 , 令 f (A , a)=B

19 有穷自动机到正规文法的转换 B C A 1 D 0,1 从状态转换图可以看出, 状态D是多余的,可以去掉,于是得到与M等价的DFA M’的状态转换图如图所示。 B C A 1

20 或 G=({A,B,C},{0,1}, P, A)其中P为 A→0B | 0 A→0B B→1C B→1C | ε C→0B | 0
例2 设DFA M=({A,B,C,D},{0,1}, δ, A,{B}) 其中： δ (A,0)=B δ (A,1)=D δ (B,0)=D δ (B,1)=C δ (C,0)=B δ (C,1)=D δ (D,0)=D δ (D,1)=D G=({A,B,C},{0,1}, P, A)其中P为 A→0B | 0 A→0B 或 B→1C B→1C | ε C→0B | 0 C→0B B C A 1

21 该自动机所识别的语言为 0(10)*。 3.5.3 有穷自动机到正规文法的转换 C A 1 B 根据转换规则所求右线性文法为
1 根据转换规则所求右线性文法为 G=({A,B,C},{0,1}, P, A)其中P为 A→0B | 0 A→0B 或 B→1C B→1C | ε C→0B | 0 C→0B 该自动机所识别的语言为 0(10)*。

22 3.6 词法分析程序的编写方法 构造词法分析程序的方法:
3.6 词法分析程序的编写方法 构造词法分析程序的方法: 第一种方法是用手工方式，即根据识别语言单词的状态转换图，使用某种高级语言，例如C语言直接编写词法分析程序。 第二种方法是利用词法分析程序的自动生成工具LEX自动生成词法分析程序，本书附录对LEX作了简单介绍。 下面以某种简单语言为例，对第一种方法作简要的介绍。

23 例如，下表列出了某个简单语言的所有单词符号，以及它们的种别编码和单词值。
1 2 3 4 5 6 7 10 11 13 14 15 16 17 18 19 21 22 23 内部字符串 二进制数值表示 begin end if then else while do 标识符 整常数 + - * / <= <> < : := ;

24 右图是一张识别前表的单词符号的状态转换图。
图中, 状态0为初态, 凡带双圈者均为终态; 状态17是识别不出单词符号的出错情况。 l 代表任一字母，d 代表任一数字。 根据这张转换图，我们用C语言直接编写出识别该语言所有单词的词法分析程序。

25 3.6 词法分析程序的编写方法 在例中，我们规定所有关键字, 用户不得使用它们作为自己定义的标识符，这样我们可以把关键字作为一类特殊的标识符来处理，不再专设对应的转换图。但需把它们预先安排在一个表格中，此表叫关键字表。当利用状态转换图识别出一个标识符时，就去查关键字表，以确定它是否是一个关键字。 其次规定，若关键字、标识符和常数之间没有确定的运算符或界符作间隔，则必须至少用一个空白符作间隔，即此时的空白符是有意义的。

26 根据状态转换图构造出词法分析程序最简单的办法是让每个状态对应一小段程序。
首先，我们引进词法分析程序所用的全局变量和需调用的函数如下： 1. ch 字符变量，存放当前读进的源程序字符。 2. token 字符数组, 存放构成单词符号的字符串。 3. getch( )读字符函数，每调用一次从输入缓冲区中读进源程序的下一个字符放在ch中，并把读字符指针指向下一个字符。 4. getbc( )函数，每次调用时，检查ch中的字符是否为空白字符，若是空白字符，则反复调用getbc( )，直至ch中进入一个非空白字符为止。

27 3.6 词法分析程序的编写方法 5. concat( )函数，每次调用把当前ch中的字符与token中的字符串联接。例如，假定token字符数组中原有值为 “ab”, ch中存放着 “c”,经调用concat( )后，token数组中的值变为“abc”。 6. letter(ch) 和 digit(ch)布尔函数，它们分别判定 ch 中的字符是否为字母和数字， 从而给出true 或 false。 7. reserve( )整型函数，对token中的字符串查关键字表，若它是一个关键字, 则回送它的编码，否则回送标识符的种别码10。

28 3.6 词法分析程序的编写方法 8. retract( )函数，读字符指针回退一个字符。
3.6 词法分析程序的编写方法 8. retract( )函数，读字符指针回退一个字符。 9. return( )函数，收集并携带必要的信息返回调用程序，即返回语法分析程序。 10. dtb( ) ＋进制转换函数, 它将token中的数字串转换成二进制数值表示, 并以此作为函数值返回。 根据该语言的状态转换图用C语言编写出词法分析程序如下:

29 Scaner( ) { token=NULL; getch( ); getbc( ); if (letter(ch)) { while(letter(ch) || digit(ch)) { concat( ); } retract( ); c=reserve( ); return(c,token);

30 相对于状态转换图用C语言编写出词法分析程序如下:
else if(digit(ch)) { while (digit(ch)) concat( ); getch( ); } retract( ); return(11,dtb( ));

31 else switch(ch) { case’+’: return(13, ―); break ; case’-’: return(14, ―); break ; case’*’: return(15, ―); break ; case’/’: return(16, ―); break ; case’<’: getch( ); if (ch= = `=´) return(17, ―); else if(ch= = `>´) return(18, ―); retract( ); return(19, ―); break; case’: ’: getch( ); if(ch= = ’=’) return(22, ―); retract( ); return(21, ―); break; case’;’: return(23, ―); break; default: error( ); break; }

32 3.6 词法分析程序的编写方法 由此可知, 只要构造出识别语言单词符号的有穷自动机, 就很容易构造出识别语言单词符号的词法分析程序。

33 习题 第三章 3.1(1) , (3)/3.3/3.5/3.11/3.12

34 本章小结 本章重点介绍了词法分析程序的设计思想和构造方法。主要内容有：
1. 词法分析程序的功能是从左到右扫描源程序字符串，根据语言的词法规则识别出各类单词符号。 输出单词符号的形式是二元组: （单词种别，单词自身值）

35 本章小结 正规文法 2．程序语言单词符号的两种定义方式 正规式 正规文法是 ＜标识符＞→ l |＜标识符＞l | ＜标识符＞d

36 本章小结 3．有穷自动机有确定的和非确定两大类： DFA M = (Q , Σ , f , S , Z )其中是f单值映射函数，S是唯一初态
NFA N = (Q , Σ , f , S , Z )其中f是多值映射函数，S为非空初态集。 有穷自动机通常表示为状态转换图，它是有穷自动机的非形式化描述。

37 本章小结 从单词两种定义方式中构造词法分析程序的过程是： 正规式 正规文法 NFA DFA 状态 最小化 词法 分析 程序 分裂法 子集法
转换规则 子集法 DFA 分划法 状态 最小化 词法 分析 程序

38 本章小结 4．正规式、正规文法和有穷自动机三者都是描述正规集的工具, 它们的描述能力是等价的，它们之间可相互转换。
5．证明两正规式是等价的,如果它们的最小状态DFA是相同的。也可以利用正规式的基本等价关系将一个正规式化简来证明两正规式之间的等价性或两正规式识别的语言一样。

39 本章小结 例1 构造正规式R=1(0|1)*101的状态最小化的DFA 分析 首先对R采用分裂法构造NFA，见下图: 5 4 3 2 1 X
Y 5 4 3 2 1 X ε

40 对NFA采用子集法构造其等价的DFA的状态转换矩阵,见右表
Y 5 4 3 2 1 X ε 对NFA采用子集法构造其等价的DFA的状态转换矩阵,见右表 字符 1 状态 A F B C D E {X} Φ {1,2,3} {1,2,3} {2,3} {2,3,4} {2,3} {2,3} {2,3,4} {2,3,4} {2,3,5} {2,3,4} {2,3,5} {2,3} {2,3,4,Y} {2,3,4,Y} {2,3,5} {2,3,4}

41 本章小结 对DFA采用分划的方法化简，得到状态最小化的DFA，见下图 : D C B A 1 字符 1 状态 A {X} Φ B
E 字符 状态 1 {X} {1,2,3} {2,3,4} {2,3,5} {2,3,4,Y} {2,3} Φ {2,3}B {2,3,4}C {2,3,5}D {2,3,4,Y}E 对DFA采用分划的方法化简，得到状态最小化的DFA，见下图 : E D C B A 1

42 例2. 给出下述文法所对应的正规式： (略) S→0A | 1B A→1S | 1 B→0S | 0 分析 根据正规文法转换成正规式的方法，首先给出该 正规文法对应的正规式方程组： S=0A+1B (1) A=1S (2) B=0S (3) 将(2)、(3)代入(1)得 S=01S+01+10S (4) 对(4)使用求解规则得 S=(01|10)(01|10)＊ 即正规文法所生成语言的正规式是(01|10)(01|10)＊。

43 本章小结 a,b 1 a b 1 a 例3 将右图确定化和最小化。 图示是一个无ε 边转移的NFA,采用子集法将NFA确定化为DFA
1 a,b a 例3 将右图确定化和最小化。 图示是一个无ε 边转移的NFA,采用子集法将NFA确定化为DFA 采用分化方法将DFA化简 字符 a b 状态 1 a b {0} {0,1} {1} {0,1} {0,1} {1} {1} {0} Φ