编译原理重点精选文档.ppt

《编译原理重点精选文档.ppt》由会员分享，可在线阅读，更多相关《编译原理重点精选文档.ppt（117页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、编译原理重点本讲稿第一页，共一百一十七页有穷自动机有穷自动机 有穷自动机（或有限自动机）作为一种识别工具，有穷自动机（或有限自动机）作为一种识别工具，它能正确地识别正规集，即识别正规文法所定义的语它能正确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合。引入有穷自动机这个理论，言和正规式所表示的集合。引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工正是为词法分析程序的自动构造寻找特殊的方法和工具。具。分类：确定的有穷自动机（分类：确定的有穷自动机（DFA）不确定的有穷自动机（不确定的有穷自动机（NFA）本讲稿第二页，共一百一十七页3.1 概述概述 有穷自动机（

2、有穷自动机（FA）有穷自动机（有穷自动机（FA，Finite Automata）是一种有限离散数字系统）是一种有限离散数字系统的抽象数学模型。的抽象数学模型。这个系统具有有限数目的内部这个系统具有有限数目的内部“状态状态”。所谓状态，是可以将事物区分开的一种标识。例如：数字电路（所谓状态，是可以将事物区分开的一种标识。例如：数字电路（0，1），十字路口的红绿灯等都是离散状态系统，其状态数目是有），十字路口的红绿灯等都是离散状态系统，其状态数目是有限的。连续状态系统则如水库的水位、室内温度变化等。限的。连续状态系统则如水库的水位、室内温度变化等。电梯的控制机制，不需要保存所有以前的服务要求，仅需

3、记电梯的控制机制，不需要保存所有以前的服务要求，仅需记住当前的层次、运动的方向以及未满足的服务要求。住当前的层次、运动的方向以及未满足的服务要求。文本编辑程序和词法分析程序是有限状态系统，计算机本身和文本编辑程序和词法分析程序是有限状态系统，计算机本身和人的大脑也可看成有限状态系统。人的大脑也可看成有限状态系统。本讲稿第三页，共一百一十七页例例 过河问题过河问题 题目题目 一个人带着一头狼、一头羊以及一棵青菜，处于河的左岸，需一个人带着一头狼、一头羊以及一棵青菜，处于河的左岸，需要渡到河的右岸。有一条小船，每次只能携带人和其余的三者之一。要渡到河的右岸。有一条小船，每次只能携带人和其余的三者之

4、一。不能让狼和羊单独在一起，无论在左岸还是右岸，否则狼会吃掉羊。不能让狼和羊单独在一起，无论在左岸还是右岸，否则狼会吃掉羊。同样，也不能让羊和青菜单独一起。同样，也不能让羊和青菜单独一起。如何才能安全渡过河呢？如何才能安全渡过河呢？本讲稿第四页，共一百一十七页例例 过河问题过河问题 分析分析 观察每次摆渡后河两岸的局势，使问题模型化。观察每次摆渡后河两岸的局势，使问题模型化。人（人（M），狼（），狼（W），羊（），羊（G），菜（），菜（C）。存在有）。存在有16种种子集，用连字号子集，用连字号”-”连接子集的对偶表示状态，例如：连接子集的对偶表示状态，例如：MG-WC，表示：人和羊在左岸，狼和

5、菜在右岸。，表示：人和羊在左岸，狼和菜在右岸。16种状态中的某些状态，是不应该引入系统的，例如种状态中的某些状态，是不应该引入系统的，例如GC-MW，有关死活。，有关死活。人所进行的摆渡活动，可作为系统的输入。人可单独过河人所进行的摆渡活动，可作为系统的输入。人可单独过河（输入为（输入为M），带着狼过河（输入为），带着狼过河（输入为W），带着羊过河（输入为），带着羊过河（输入为G）或者是带着菜过河（输入为）或者是带着菜过河（输入为C）。）。问题问题：初始状态应该是什么？终止状态应该是什么？：初始状态应该是什么？终止状态应该是什么？本讲稿第五页，共一百一十七页例例 过河问题过河问题 分析（续）分

6、析（续）初始状态：初始状态：MWGC-；终止状态：；终止状态：-MWGC。MWGC-WC-MGg 问题：问题：本讲稿第六页，共一百一十七页例例 过河问题过河问题 状态转换图状态转换图MWGC-WC-MGC-MWGMWG-CMGC-WG-MWCMG-WC-MWGCW-MGCMWC-Gggggmggggmmmccccwwww起始起始本讲稿第七页，共一百一十七页有穷自动机（有穷自动机（FA）数字系统：可以从一个状态移动到另一个状态；每次状态转数字系统：可以从一个状态移动到另一个状态；每次状态转换，都上由当前状态及一组输入符号确定的；可以输出某些离散换，都上由当前状态及一组输入符号确定的；可以输出某些

7、离散的值集。的值集。FA：一个状态集合；状态间的转换规则；通过读头来扫描的一：一个状态集合；状态间的转换规则；通过读头来扫描的一个输入符号串。个输入符号串。读头：从左到右扫描符号串。移动（扫描）是由状态转读头：从左到右扫描符号串。移动（扫描）是由状态转换规则来决定的。换规则来决定的。本讲稿第八页，共一百一十七页ddd;.dd+;输入符号串一个FA的例子读头数字A数字+-.SGBH数字数字.数字接收：若扫描完输入串，接收：若扫描完输入串，且在一个终止状态上结束。且在一个终止状态上结束。阻塞：若扫描结束但未停止阻塞：若扫描结束但未停止在终止状态上；或者为能扫在终止状态上；或者为能扫描完输入串（如遇

8、不合法符描完输入串（如遇不合法符号）。号）。不完全描述：某些状态对于不完全描述：某些状态对于某些输入符号不存在转换。某些输入符号不存在转换。练习练习：+34.567 .123 3.4.5本讲稿第九页，共一百一十七页=80;0134256eniL字母字母字母字母数字数字数字=；0124563Line=80;id,Line=,num,80;,数字数字字母字母1 1=0003;1输入符号串输出有限控制器读头本讲稿第十页，共一百一十七页3.2 有穷自动机的形式定义有穷自动机的形式定义DFA:Deterministic Finite AutomataNFA:Nondeterministic Finite

9、 AutomataDFA的定义的定义定义定义3.1 一个确定的有穷自动机一个确定的有穷自动机(DFA)M是一个五元组：是一个五元组：M=(K,f,S,Z)(1)K是一个非空有穷集合，它的每一个元素称为一个状态；是一个非空有穷集合，它的每一个元素称为一个状态；(2)是一个有穷字母表，它的每一个元素称为一个输入字符；是一个有穷字母表，它的每一个元素称为一个输入字符；也也称为输入符号字母表称为输入符号字母表本讲稿第十一页，共一百一十七页确定的有穷自动机确定的有穷自动机DFA的定义（续）的定义（续）(3)f是从是从K到到K的单值部分映射；的单值部分映射；f(ki,a)=kj，其中其中ki K，kj K

10、说明：当前状态为说明：当前状态为ki，输入字符，输入字符a时，将转换到下一个状态时，将转换到下一个状态kj，把，把kj称为称为ki的一个后继状态。的一个后继状态。DFA的确定性就表现在的确定性就表现在f是单值函数，即对任意状态是单值函数，即对任意状态k K，输入符，输入符号号a，f(k,a)唯一确定一个状态。唯一确定一个状态。(4)S K，是唯一的初态；，是唯一的初态；(5)Z是是K的子集，是一个终态集，终态也称为可接收状态或结束状态的子集，是一个终态集，终态也称为可接收状态或结束状态。本讲稿第十二页，共一百一十七页确定的有穷自动机确定的有穷自动机DFA的表示的表示 3.2.1 状态转换图状态

11、转换图 设设DFA有有m个状态，个状态，n个输入字符，那么这个图含有个输入字符，那么这个图含有m个状态个状态结，每个结点最多有结，每个结点最多有n条箭弧射出和别的结点相连接，每条弧用条箭弧射出和别的结点相连接，每条弧用中的一个不同输入符号作记号。整个图含有唯一的一个初态和若中的一个不同输入符号作记号。整个图含有唯一的一个初态和若干个（可以干个（可以0个）终态结。个）终态结。习惯上，初态结可以用习惯上，初态结可以用“=”或或“”表示，终态结用双圆表示，终态结用双圆圈表示或标以圈表示或标以“+”。对。对f(ki,a)=kj指从状态结指从状态结ki到状态结到状态结kj画标记画标记a的弧。的弧。本讲稿

12、第十三页，共一百一十七页 例例题：题：DFA M=(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解：该解：该DFA M的状态图：的状态图：0123abbaaba,b本讲稿第十四页，共一百一十七页确定的有穷自动机确定的有穷自动机DFA的表示（续）的表示（续）3.2.2 状态转换矩阵状态转换矩阵 矩阵的行表示状态，列表示输入字符，矩阵矩阵的行表示状态，列表示输入字符，矩阵元素表示相应的状态行在输入字符列下的新的状元素表示相应的状态行在输

13、入字符列下的新的状态，即态，即f(k,a)的值。的值。本讲稿第十五页，共一百一十七页例（题同）例（题同）解：该解：该DFA M的矩阵表示的矩阵表示状态状态 字符字符ab0121322133330123abbaaba,b0 0 0 1 本讲稿第十六页，共一百一十七页3.2.3 有关自动机术语有关自动机术语(1)道路：对于道路：对于*中的任何字中的任何字，若存在一条从初态到某终态的，若存在一条从初态到某终态的路径。路径。(2)识别：道路上所有弧的标记连接成的字等于识别：道路上所有弧的标记连接成的字等于，则称，则称可为可为DFA M所识别（所接受）。所识别（所接受）。即若即若t*,f(S,t)=P，

14、其中，其中S为为DFA M的初始状态，的初始状态，P Z（终态（终态集）。集）。若若M的初态结同时也是终态结，则空字的初态结同时也是终态结，则空字可为可为M所识别，即所识别，即Q K,f(Q,)=Q(3)运行：运行：f(Q,t1t2)=f(f(Q,t1),t2)，其中，其中QK，t1t2为输入字符串，且为输入字符串，且t1，t1t2*本讲稿第十七页，共一百一十七页例例解：解：f(0,abba)=f(f(0,a),bba)=f(1,bba)=f(f(1,b),ba)=f(2,ba)=f(f(2,b),a)=f(3,a)=3 得证得证题：试证题：试证abba可为例可为例1的的DFA M所识别（所接

15、受）。所识别（所接受）。0123abbaaba,b本讲稿第十八页，共一百一十七页 3.2.4 有关确定有穷自动机的结论有关确定有穷自动机的结论 把把DFA M所能接受的所有字（字的全体）记为所能接受的所有字（字的全体）记为L(M)。上的一个字集上的一个字集V*是正规的，当且仅当存在一个是正规的，当且仅当存在一个上的确定有穷自动机上的确定有穷自动机M，使得，使得L(M)=V。本讲稿第十九页，共一百一十七页有限自动机识别的语言有限自动机识别的语言 例子例子 例：下图中的自动机所能识别的语言是什么？例：下图中的自动机所能识别的语言是什么？q0q2q1q3abbaba本讲稿第二十页，共一百一十七页 定

16、义定义3.4 一个不确定的有穷自动机一个不确定的有穷自动机NFA N也是一个五元组：也是一个五元组：M=(K,f,S,Z)(1)K是一个有穷集合，它的每一个元素称为一个状态；是一个有穷集合，它的每一个元素称为一个状态；(2)是一个有穷字母表，它的每一个元素称为一个输入字符；是一个有穷字母表，它的每一个元素称为一个输入字符；也称为也称为输入符号字母表输入符号字母表(3)f是一个是一个K*到到K的子集的映射：的子集的映射：f:K*2k(4)S是是K的子集，是非空的初态集；的子集，是非空的初态集；(5)Z是是K的子集，是一个终态集，也称可接收状态或结束状态。的子集，是一个终态集，也称可接收状态或结束

17、状态。3.2.5 不确定的有穷自动机不确定的有穷自动机(NFA)的定义的定义本讲稿第二十一页，共一百一十七页NFA的表示用状态转换图（用状态转换图（f是多值函数）是多值函数）由由NFA的定义，可把一个含有的定义，可把一个含有m个状态和个状态和n个输入字符的个输入字符的NFA表表示如下：示如下：图中有图中有m个状态结，对每个状态结可射出若干条弧和别的状个状态结，对每个状态结可射出若干条弧和别的状态结相连，且每条弧用态结相连，且每条弧用*中的一个字（不一定要不同的字且中的一个字（不一定要不同的字且可以是空字可以是空字）作标记（或称输入字）。整个图中至少含有一个初）作标记（或称输入字）。整个图中至少

18、含有一个初态结以及若干个（可以是态结以及若干个（可以是0个）终态结。个）终态结。某些结既可以是初态结也可以是终态结。某些结既可以是初态结也可以是终态结。本讲稿第二十二页，共一百一十七页例例题：一个题：一个NFA M(s,t，0,1，f，s，t)，其中，其中 f(s,0)=s,t,f(s,1)=t,f(t,0)=,f(t,1)=s,t,解：其状态图如下：解：其状态图如下：s0t0111本讲稿第二十三页，共一百一十七页例例如下状态图也是一个如下状态图也是一个NFA0a,b1aabba,b2a,b本讲稿第二十四页，共一百一十七页有关非确定有穷自动机的术语有关非确定有穷自动机的术语对于对于*中的任何一

19、个串中的任何一个串t可被可被NFA M识别是指：若对识别是指：若对这个字（串）这个字（串）t存在一条从某个初态结到某一个终态结存在一条从某个初态结到某一个终态结的道路，且这条道路上所有弧的标记字依序连接起来的道路，且这条道路上所有弧的标记字依序连接起来的字（不理睬那些标记为的字（不理睬那些标记为的弧）等于的弧）等于t，则，则t可识别可识别（或可接受）（或可接受）若若M的某些结点既是初态结也是终态结，或存在一的某些结点既是初态结也是终态结，或存在一条从某个初态结到某个终态结的条从某个初态结到某个终态结的道路，则空字道路，则空字可为可为M所识别（所接受）。所识别（所接受）。本讲稿第二十五页，共一百

20、一十七页补充：递归思想构造文法补充：递归思想构造文法 在某些复杂的语言中，字符串可能包含一种结构，它递在某些复杂的语言中，字符串可能包含一种结构，它递归地作为另一种（或者同一种）结构的一部分而出现，可利归地作为另一种（或者同一种）结构的一部分而出现，可利用递归思想来构造对应的文法。用递归思想来构造对应的文法。例例1：定义语言：定义语言L=|中中a和和b的个数相同的个数相同的文法。的文法。解：先构造出基础情况的文法：解：先构造出基础情况的文法：S-ab|ba|再递归地构造出归纳情况的文法（新的生成式不能改变再递归地构造出归纳情况的文法（新的生成式不能改变a和和b的个数的个数关系）：关系）：S-S

21、ab|aSb|abS|Sba|bSa|baS本讲稿第二十六页，共一百一十七页递归思想构造文法递归思想构造文法（续）（续）例例1：求一个文法求一个文法G，使得，使得(G)即该文法的语言是奇数个和奇数即该文法的语言是奇数个和奇数个的组合个的组合。解：解：因为语言是奇数个和奇数个的组合，所以打头的最小语言因为语言是奇数个和奇数个的组合，所以打头的最小语言有四种组合：有四种组合：aa bb ab ba定义定义S和和A，S是表示奇数个是表示奇数个 a和奇数个和奇数个b的组合，而的组合，而A是表示是表示偶数个偶数个a和偶数个和偶数个b的组合。的组合。开始递归构造文法：开始递归构造文法：S-aaS|bbS|

22、abA|baA A-aaA|bbA|abS|baS|本讲稿第二十七页，共一百一十七页补充：如何设计有限自动机补充：如何设计有限自动机 如同文法的设计，自动机的设计也是一个创造过程。如同文法的设计，自动机的设计也是一个创造过程。有一种做法，在设计各种类型的自动机时都很有帮助，即有一种做法，在设计各种类型的自动机时都很有帮助，即采用一种心理上的技巧，采用一种心理上的技巧，把自己放在要设计的机器的位置把自己放在要设计的机器的位置上，考虑自己该如何实现自动机的任务上，考虑自己该如何实现自动机的任务。假定自己是一台有限自动机，接受到一个输入符号串时，假定自己是一台有限自动机，接受到一个输入符号串时，必须

23、确定到目前为止所看到的字符串是否可为该自动机所识必须确定到目前为止所看到的字符串是否可为该自动机所识别。为了能够判断这一点，必须估算出识别时需要记住哪些别。为了能够判断这一点，必须估算出识别时需要记住哪些关键的东西。关键的东西。为什么不记住所有看到的东西呢？因为你是一台有限自动机，为什么不记住所有看到的东西呢？因为你是一台有限自动机，只有有限个状态，而这些状态是你记住事情的唯一办法。输入串可只有有限个状态，而这些状态是你记住事情的唯一办法。输入串可能很长，而你不可能记住所有的事情。能很长，而你不可能记住所有的事情。幸运的是，许多语言只需要记住某些关键的信息就可幸运的是，许多语言只需要记住某些关

24、键的信息就可以了。以了。本讲稿第二十八页，共一百一十七页设计有限自动机（续设计有限自动机（续1）例例1：构造一台有限自动机，识别所有由奇数个：构造一台有限自动机，识别所有由奇数个a和奇数个和奇数个b组成的字符串。组成的字符串。解：为了确定解：为了确定a和和b的个数是否是奇数，不需要记住所看的个数是否是奇数，不需要记住所看到的整个字符串，而只需要记住至此所看到的到的整个字符串，而只需要记住至此所看到的a、b个个数是偶数还是奇数即可。一旦确定了关键信息，就可数是偶数还是奇数即可。一旦确定了关键信息，就可以开始设计状态了。以开始设计状态了。这些信息有如下四种可能性：这些信息有如下四种可能性：本讲稿第

25、二十九页，共一百一十七页设计有限自动机（续设计有限自动机（续2）例例1：(1)到此为止是偶数个到此为止是偶数个a和偶数个和偶数个b;(2)到此为止是奇数个到此为止是奇数个a和偶数个和偶数个b;(3)到此为止是偶数个到此为止是偶数个a和奇数个和奇数个b;(4)到此为止是奇数个到此为止是奇数个a和奇数个和奇数个b。根据每种可能性设计一个状态，并根据可能的输入符号来设根据每种可能性设计一个状态，并根据可能的输入符号来设计状态之间的转移条件。计状态之间的转移条件。1324aaaabbbb本讲稿第三十页，共一百一十七页设计有限自动机（续设计有限自动机（续3）例例2：设计有限自动机：设计有限自动机M，识别

26、含有，识别含有00作为子串的作为子串的所有所有0，1*上的字符串组成的语言。上的字符串组成的语言。如：如：0010，1001，110001001解：解：3种可能性：种可能性：(1)到此为止未看到模式到此为止未看到模式“00”的任何符号的任何符号;(2)到此为止看见了一个到此为止看见了一个0;(3)到此为止已经看见整个模式到此为止已经看见整个模式“00”。本讲稿第三十一页，共一百一十七页设计有限自动机（续设计有限自动机（续4）例例2自动机的状态转换图为：自动机的状态转换图为：qq0q0010,1100或者为（或者为（NFA）：）：qq0q000,10,100本讲稿第三十二页，共一百一十七页设计有

27、限自动机（续设计有限自动机（续5）例例3 构造一个有穷自动机构造一个有穷自动机M，识别所有形如，识别所有形如0k的的字符串，其中字符串，其中k是是2或或3的倍数。的倍数。（2）识别）识别0k的字符串，其中的字符串，其中k是是3的倍数：的倍数：00000（1）识别）识别0k的字符串，其中的字符串，其中k是是2的倍数：的倍数：本讲稿第三十三页，共一百一十七页设计有限自动机（续设计有限自动机（续6）例例3 的有穷自动机的有穷自动机M为：为：s0000000000 以上两个自动机是否以上两个自动机是否等价？等价？这个自动机显示了这个自动机显示了转换的方便之处。转换的方便之处。本讲稿第三十四页，共一百一

28、十七页设计有限自动机（续设计有限自动机（续7）1.思考题：思考题：构造一个有穷自动机构造一个有穷自动机M，识别，识别0，1，2上的语言，该语言的每个字符串代表的十进制上的语言，该语言的每个字符串代表的十进制数能被数能被3整除。整除。如：如：102，1020，10201，110,2.编程题：根据有穷自动机编程题：根据有穷自动机M，编写程序，识别所有由，编写程序，识别所有由奇数个奇数个a和奇数个和奇数个b组成的字符串。组成的字符串。1324aaaabbbb(1)用户输入：用户输入：ab组成的组成的符号串；符号串；(2)一个字符一个字符地一个字符一个字符地读、分析；读、分析；(3)不要使用计数器。不

29、要使用计数器。本讲稿第三十五页，共一百一十七页设计有限自动机（续设计有限自动机（续8）1.思考题：思考题：构造一个有穷自动机构造一个有穷自动机M，识别，识别0，1，2上的语言，该语言的每个字符串代表的十进制上的语言，该语言的每个字符串代表的十进制数能被数能被3整除。整除。如：如：102，1020，10201，110,思路思路(1):所有位数之和所有位数之和；(2):q0:3n+0 q1:3n+1 q2:3n+2q0+1-q1，因，因(3n+0)*10+1)/3余余1；q1+1-q2，因，因(3n+1)*10+1)/3余余2；.q0q1q2121201200本讲稿第三十六页，共一百一十七页NFA

30、和和DFA的关系的关系 DFA是是NFA的一个特例。的一个特例。l 对于每个对于每个NFA M，存在一个，存在一个DFA M，使得，使得L(M)=L(M)l 对于任何两个有穷自动机对于任何两个有穷自动机M和和M，如，如L(M)=L(M)则称则称M和和M是是等价等价的。的。l如果如果M仅通过重新标记它的状态，就能转换成仅通过重新标记它的状态，就能转换成M，则，则M和和M称为同构的。称为同构的。l对于每一个对于每一个FA M，存在一个等价的、具有最少状态个数的，存在一个等价的、具有最少状态个数的FA M，对于其它的，对于其它的FA M，若，若M的状态个数与的状态个数与M相同且等价相同且等价与与M，

31、则必然有，则必然有M与与M同构，即：同构，即：M在结构上是唯一的。在结构上是唯一的。本讲稿第三十七页，共一百一十七页3.3 NFA DFA的转换（的转换（NFA的确定化）的确定化）通过以下步骤，可以将一个通过以下步骤，可以将一个NFA转换为等价的转换为等价的DFA：1.寻找并消除空移环路；寻找并消除空移环路；2.消除余下的空移；消除余下的空移；3.确定化。确定化。本讲稿第三十八页，共一百一十七页 3.3.1 NFA中空移环路的寻找和消除中空移环路的寻找和消除空移环路：空移环路：一个空移环路，是一个从状态一个空移环路，是一个从状态A开始，并以状态开始，并以状态A结束的结束的空移动序列。空移动序列

32、。q1q2q1q2q3q1q2q3qn消除方法：消除方法：合并环路上的结合并环路上的结点为新结点。点为新结点。若含初态，则新若含初态，则新结点为初态。结点为初态。若含终态，则新若含终态，则新结点为终态。结点为终态。课本课本P56 例例3.4本讲稿第三十九页，共一百一十七页 3.3.2 NFA的消除空移ABa1q1q2qna2anABa1q1q2qna2ana1a2an消除方法：消除方法：删除删除弧，产生新弧。弧，产生新弧。若若A为初态，则为初态，则B结点也为初态。结点也为初态。若若B为终态，则为终态，则A结点也为终态。结点也为终态。本讲稿第四十页，共一百一十七页3.3.4 NFA的确定化子集法

33、 添加一个例子添加一个例子(无空移无空移)介绍一种称介绍一种称子集法子集法的算法来将的算法来将NFA转换成接收同转换成接收同样语言的样语言的DFA。算法的基本思想是：把算法的基本思想是：把DFA中的每一个状态对应中的每一个状态对应NFA中的一组状态。即由于中的一组状态。即由于NFA中的中的f是多值的，所以是多值的，所以在读入一个输入符号后可能达到的状态是集合，而子集在读入一个输入符号后可能达到的状态是集合，而子集法就是用法就是用DFA的状态记录该状态的集合。的状态记录该状态的集合。本讲稿第四十一页，共一百一十七页确定化的有关运算确定化的有关运算（2）Move(I,a)状态集合状态集合I的的a弧

34、转换弧转换 假定假定I是状态集的一个子集，是状态集的一个子集，a是是中的一个字符，定义中的一个字符，定义 Ia _closure(J)其中其中J是所有那些可从是所有那些可从I中的某一状态出发经过一条中的某一状态出发经过一条a弧而到达的状态结的弧而到达的状态结的全体。全体。(3)Ia _closure(Move(I,a)（1）_closure(I)状态集合状态集合I的的闭包闭包(等价状态集等价状态集)设设I是状态集的一个子集，是状态集的一个子集，_closure(I)定义为：定义为：a.若若SI，则，则S _closure(I)；b.若若SI，那么从，那么从S出发经过任意出发经过任意弧而能到达的

35、任意状态弧而能到达的任意状态S都都属于属于_closure(I)；本讲稿第四十二页，共一百一十七页题：有一个状态图如下：题：有一个状态图如下：1526a4a73a8假定假定 I=_closure(1)1,2从状态集从状态集I出发经过一条出发经过一条a弧而能到达的状态结全体弧而能到达的状态结全体J为为5,3,4；而而_closure(J)=5,6,2,3,8,4,7例例本讲稿第四十三页，共一百一十七页NFA的确定化的确定化 从从NFA N(K,f,K0,Kt)构造一个构造一个DFA M(S,D,S0,St)，其中，其中 (1)S是由是由K一些子集组成；一些子集组成；(2)M与与N的输入字母表相同

36、，都是的输入字母表相同，都是；(3)D定义：定义：D(S1,S2,Sj,a)=R1,R2,Ri，其中，其中 _closure(move(S1,S2,Sj,a)=R1,R2,Ri (4)S0=_closure(K0)为为M的开始符号（初态）；的开始符号（初态）；(5)St=Sj,Sk,Se，其中，其中Sj,Sk,Se S且且Sj,Sk,SeKt 本讲稿第四十四页，共一百一十七页子集化的具体过程子集化的具体过程为了方便起见，令为了方便起见，令中只有中只有a,b两个字母，即两个字母，即a,b（1）构造一张表，此表的每一行有三列，第一列为）构造一张表，此表的每一行有三列，第一列为I，第二列为，第二列为

37、Ia，第二列为第二列为Ib。即。即I IIaIb_closure(K0)首先置该表的第一列为首先置该表的第一列为_closure(K0)。（2）一般而言，若某一行的第一列的状态子集已确定，例如记为）一般而言，若某一行的第一列的状态子集已确定，例如记为I，则可以求出则可以求出Ia和和Ib；本讲稿第四十五页，共一百一十七页子集化的具体过程（续）子集化的具体过程（续）（3）检查）检查Ia和和Ib是否已在表的第一列中出现，把未曾出现者填入是否已在表的第一列中出现，把未曾出现者填入到后面空行的第一列位置上。到后面空行的第一列位置上。（4）对未重复）对未重复Ia、Ib的新行重复上述过程的新行重复上述过程(

38、2)、(3)，直到所有，直到所有第二列和第三列的子集全部在第一列中出现；第二列和第三列的子集全部在第一列中出现；上述过程必定在有限步内终止，因为上述过程必定在有限步内终止，因为N的状态子集的个数是有的状态子集的个数是有限的。我们也可将表看成状态转换矩阵，即把其中每个子集看成限的。我们也可将表看成状态转换矩阵，即把其中每个子集看成一个状态，就可以由这张表唯一刻划出一个确定的有穷自动机一个状态，就可以由这张表唯一刻划出一个确定的有穷自动机DFA。其初态就是该表的第一行第一列的。其初态就是该表的第一行第一列的_closure(K0)，终态就是那，终态就是那些含有的些含有的Kt子集。子集。本讲稿第四十

39、六页，共一百一十七页例例题：将下图题：将下图NFA N确定化。确定化。12b3a7045b68a910bIIaIbSab0,1,2,4,71,2,3,4,6,7,81,2,4,5,6,70121,2,3,4,6,7,81,2,3,4,6,7,81,2,4,5,6,7,91131,2,4,5,6,71,2,3,4,6,7,81,2,4,5,6,72121,2,4,5,6,7,91,2,3,4,6,7,8 1,2,4,5,6,7,103141,2,4,5,6,7,10 1,2,3,4,6,7,81,2,4,5,6,7412解：(1)构造转换矩阵构造转换矩阵本讲稿第四十七页，共一百一十七页 接上页接

40、上页(2)对表中所有的子集重新命名，其中对表中所有的子集重新命名，其中0是初态，是初态，4是终态。是终态。对应的对应的DFA M：0124ba3aabbabab本讲稿第四十八页，共一百一十七页例例题：将下图确定化：题：将下图确定化：解：解：(1)构造转换矩阵构造转换矩阵II0I1S01s,x,yws,x,yABAw y,s,x,zBCs,x,y,zw,s,x,ys,x,yCDAw,s,x,yws,x,y,zDBCsyxwz10101本讲稿第四十九页，共一百一十七页接上页接上页 DFA M为：为：ABDC0110101本讲稿第五十页，共一百一十七页3.3.6 消除不可达状态 有穷自动机的有穷自动

41、机的多余状态多余状态：是指这样的状态，从该自动机的开：是指这样的状态，从该自动机的开始状态出发，任何输入串也不能达到的那个状态。始状态出发，任何输入串也不能达到的那个状态。01S0S1S5S1S2S7S2S2S5S3S5S7S4S5S6S5S3S1S6S8S0S7S0S1S8S3S6本讲稿第五十一页，共一百一十七页3.3.7 DFA的化简的化简 对已求得的对已求得的DFA，可以进一步将其化简，即求最小，可以进一步将其化简，即求最小DFA。也。也就是对于任意给定的就是对于任意给定的DFA M构造另一个构造另一个DFA M，使，使L(M)=L(M)，且且DFA M的状态个数少于的状态个数少于DFA

42、 M的状态个数。的状态个数。消除多余状态消除多余状态 DFA M状态最少化的过程：状态最少化的过程：把把M的状态集分割成一些不相交的子集，使得任何不同的两个子的状态集分割成一些不相交的子集，使得任何不同的两个子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的。集的状态都是可区别的，而同一子集中的任何两个状态都是等价的。本讲稿第五十二页，共一百一十七页有关分割法所用的概念有关分割法所用的概念定义定义3.8 等价等价 设设s,t是是M的两个不同的状态，的两个不同的状态，s,t等价的意思是：如果从状态等价的意思是：如果从状态s出发出发能读出某个字能读出某个字而停于终态，那么同样从而停于终态

43、，那么同样从t出发也能读出同一个字出发也能读出同一个字而而停于终态；反之，若能从停于终态；反之，若能从t出发读出某个字出发读出某个字而停于终态，那么同样而停于终态，那么同样从从s出发也能读出字出发也能读出字而停于终态。而停于终态。等价的条件：等价的条件：(1)一致性条件一致性条件 状态状态t,s必须同时是可接受状态或不可接受状态；必须同时是可接受状态或不可接受状态；(2)蔓延性条件蔓延性条件 对于所有输入符号，状态对于所有输入符号，状态s和状态和状态t必须转换到等价的必须转换到等价的状态里状态里(注：状态注：状态s对应有输入对应有输入a而状态而状态t无输入无输入a时，这两个状态是不等价的）时，

44、这两个状态是不等价的）。本讲稿第五十三页，共一百一十七页有关分割法所用的概念有关分割法所用的概念定义定义3.9 可区分可区分 若若DFA M中的两个状态中的两个状态s,t不等价，则这两个状态是可区别的。不等价，则这两个状态是可区别的。例如：终态和非终态是可区别的（读出例如：终态和非终态是可区别的（读出）；）；下图中的状态下图中的状态2与状态与状态3（读出（读出b字）；字）；0124ba3aabbabab本讲稿第五十四页，共一百一十七页分割法分割法(1)把把K的终态和非终态分开，分成两个子集的终态和非终态分开，分成两个子集 终态组和非终态终态组和非终态组，形成基本分划组，形成基本分划；显然，属于

45、这两个不同子集的状态是可区别的。；显然，属于这两个不同子集的状态是可区别的。(2)假定到某个时候假定到某个时候含有含有m个子集，记个子集，记=I(1),I(2),I(m)，若存，若存在一个输入字符在一个输入字符a使得使得Ia(i)不全包含在现行不全包含在现行的某个子集的某个子集I(j)中，就将中，就将I(j)一分为二；至此把一分为二；至此把I(i)分成两半，形成新的划分分成两半，形成新的划分 new。本讲稿第五十五页，共一百一十七页分割法（续）分割法（续）(3)重复上述过程重复上述过程(2)，直到，直到所含的子集不再增长为止，此时得所含的子集不再增长为止，此时得到最后的划分到最后的划分 fin

46、ish；此时，此时，中的所有子集已是不可再分的了。也就是说，同个子集中的所有子集已是不可再分的了。也就是说，同个子集中的状态都是互相等价的，而不同子集中的状态则是可区别的。中的状态都是互相等价的，而不同子集中的状态则是可区别的。(4)对于对于 finish中的每一个子集，选取子集中的一个状态代表其中的每一个子集，选取子集中的一个状态代表其它状态，这个代表就是化简了的它状态，这个代表就是化简了的DFA M的状态。的状态。例如：假定例如：假定I=S1,S2,S3这样一个子集，则可选这样一个子集，则可选S1代表这个子集，代表这个子集，那么在原自动机中，凡导入到那么在原自动机中，凡导入到S2,S3的弧

47、都导入到的弧都导入到S1,然后把然后把S2,S3结点从原来的状态集合中删除，因为它们已成了一些多余的状态结点从原来的状态集合中删除，因为它们已成了一些多余的状态（从开始状态出发，任何输入串也不能达到的状态）。（从开始状态出发，任何输入串也不能达到的状态）。本讲稿第五十六页，共一百一十七页对划分的说明对划分的说明例如：假定例如：假定I(i)中的状态中的状态S1和和S2经经a弧分别到达状态弧分别到达状态t1和和t2，而，而t1和和t2属属于现行于现行中的两个不同子集，则将中的两个不同子集，则将一分为二，使得一半含有一分为二，使得一半含有S1：I(i1)=S|S I(i1)且且S经经a弧到达弧到达t

48、1，则另一半含有，则另一半含有S2：I(i2)=I(i)I(i1);由于由于t1和和t2是可区别的，即存在一个字是可区别的，即存在一个字，t1将读出将读出而停于终态，而停于终态，而而t2或读不出字或读不出字或虽可读出字或虽可读出字但不到达终态，或情况恰好相但不到达终态，或情况恰好相反。因而字反。因而字将将S1和和S2区别开来，也就是说，区别开来，也就是说，I(i1)和和I(i2)中的中的状态是可区别状态是可区别本讲稿第五十七页，共一百一十七页若若I中含有原来的初态，则中含有原来的初态，则S1是是新初态新初态；若含有；若含有原来的终态，则原来的终态，则S1是是新终态新终态。经过消除多余状态和合并

49、等价状态而得到的经过消除多余状态和合并等价状态而得到的DFA M，便是最简化的（包含最少状态的），便是最简化的（包含最少状态的）DFA。化简后初态和终态的确定化简后初态和终态的确定本讲稿第五十八页，共一百一十七页a134267=5aaaaaabbbbbbb例：化简下图中的例：化简下图中的DFA解：解：(1)把把M的状态分成两组：的状态分成两组：1,2,3,4、5,6,7；本讲稿第五十九页，共一百一十七页例：例：DFA化简化简 (2)考察考察5,6,7，由于，由于5,6,7a=4,7，因此对，因此对5,6,7一分为二：一分为二：5、6,7；(3)考察考察1,2,3,4，由于，由于1,2,3,4a

50、=1,4,6,7，因此对，因此对1,2,3,4一一分为二：分为二：1,2、3,4；(4)考察考察3,4，由于，由于3,4a=1,4，因此将，因此将3,4一分为二：一分为二：3、4；至此，整个划分为：至此，整个划分为：1,2、3、4、5、6,7。用。用1，3，4，5，6分别来代替子集分别来代替子集1,2、3、4、5、6,7 化简了的化简了的DFA M为：为：本讲稿第六十页，共一百一十七页例：化简后的例：化简后的DFA化简后的化简后的DFAaa1346=5aabbbbba本讲稿第六十一页，共一百一十七页例例思考题：将下列DFA M最小化。0124ba3aabbabab解：整个划分为：解：整个划分为