计算机科学与技术 编译原理第三章重点

1、第三章第三章 有穷自动机有穷自动机要点：要点： 1. DFA 1. DFA和和NFANFA的定义的定义 2. NFADFA 2. NFADFA的转换；的转换； 3. DFA 3. DFA的化简的化简 4. 4. 正规文法、正规式、有正规文法、正规式、有穷自动机之间的相互转换；穷自动机之间的相互转换；编译原理编译原理2有穷自动机有穷自动机 有穷自动机（或有限自动机）作为一种识别工有穷自动机（或有限自动机）作为一种识别工具，它能正确地识别正规集，即识别正规文法所定具，它能正确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合。引入有穷自动机义的语言和正规式所表示的集合。引入有穷自动机这个

2、理论，正是为词法分析程序的自动构造寻找特这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。殊的方法和工具。分类：确定的有穷自动机（分类：确定的有穷自动机（DFA） 不确定的有穷自动机（不确定的有穷自动机（NFA）33.1 概述概述 有穷自动机（有穷自动机（FA） 有穷自动机（有穷自动机（FA，Finite Automata）是一种有限离散数）是一种有限离散数字系统的抽象数学模型。字系统的抽象数学模型。 这个系统具有有限数目的内部这个系统具有有限数目的内部“状态状态”。 所谓状态，是可以将事物区分开的一种标识。例如：数所谓状态，是可以将事物区分开的一种标识。例如：数字电路（字电路（0，

3、1），十字路口的红绿灯等都是离散状态系统，），十字路口的红绿灯等都是离散状态系统，其状态数目是有限的。连续状态系统则如水库的水位、室内其状态数目是有限的。连续状态系统则如水库的水位、室内温度变化等。温度变化等。 电梯的控制机制，不需要保存所有以前的服务要求，仅电梯的控制机制，不需要保存所有以前的服务要求，仅需记住当前的层次、运动的方向以及未满足的服务要求。需记住当前的层次、运动的方向以及未满足的服务要求。 文本编辑程序和词法分析程序是有限状态系统，计算机文本编辑程序和词法分析程序是有限状态系统，计算机本身和人的大脑也可看成有限状态系统。本身和人的大脑也可看成有限状态系统。 4有穷自动机（有穷自

4、动机（FA） 数字系统：可以从一个状态移动到另一个状态；每次数字系统：可以从一个状态移动到另一个状态；每次状态转换，都上由当前状态及一组输入符号确定的；可以状态转换，都上由当前状态及一组输入符号确定的；可以输出某些离散的值集。输出某些离散的值集。 FA：一个状态集合；状态间的转换规则；通过读头来：一个状态集合；状态间的转换规则；通过读头来扫描的一个输入符号串。扫描的一个输入符号串。 读头：从左到右扫描符号串。移动（扫描）是由状态读头：从左到右扫描符号串。移动（扫描）是由状态转换规则来决定的。转换规则来决定的。5ddd;.dd+;输入符号串一个FA的例子读头数字A数字+-.SGBH数字数字.数字

5、接收：若扫描完输入串，接收：若扫描完输入串，且在一个终止状态上结且在一个终止状态上结束。束。阻塞：若扫描结束但未阻塞：若扫描结束但未停止在终止状态上；或停止在终止状态上；或者不能扫描完输入串者不能扫描完输入串（如遇不合法符号）。（如遇不合法符号）。不完全描述：某些状态不完全描述：某些状态对于某些输入符号不存对于某些输入符号不存在转换。在转换。练习练习：+34.567 .123 3.4.56= 80;0134256eniL字母字母字母字母数字数字数字= =；0124563L ine= 80; id , Line = , num, 80 ;, 数字数字字母字母1 1= =0 0 03; ;1输入符

6、号串输出有限控制器读头other73.2 有穷自动机的形式定义有穷自动机的形式定义DFA: Deterministic Finite AutomataNFA: Nondeterministic Finite AutomataDFA的定义的定义定义定义3.1 一个确定的有穷自动机一个确定的有穷自动机(DFA) M是一个五元组：是一个五元组： M = ( Q, , t, q0, F ) (1)Q是一个非空有穷集合，它的每一个元素称为一个状态；是一个非空有穷集合，它的每一个元素称为一个状态； (2)是一个有穷字母表，它的每一个元素称为一个输入字是一个有穷字母表，它的每一个元素称为一个输入字符；符；

7、也称为输入符号字母表也称为输入符号字母表8确定的有穷自动机确定的有穷自动机DFA的定义（续）的定义（续） (3) t是从是从Q到到Q的一个单值映射；的一个单值映射； t(q,a)=q， 其中其中q, qQ说明：当前状态为说明：当前状态为q ，输入字符，输入字符a时，将转换到下一个时，将转换到下一个状态状态q ，把，把q称为称为q的一个后继状态。的一个后继状态。 DFA的确定性就表现在的确定性就表现在t是单值函数，即对任意状态是单值函数，即对任意状态qQ，输入符号输入符号a，t(q,a)唯一确定一个状态。唯一确定一个状态。 (4)q0Q，是唯一的初态；，是唯一的初态； (5)F是是Q的子集，是一

8、个终态集，终态也称为可接收状态或的子集，是一个终态集，终态也称为可接收状态或结束状态结束状态。9确定的有穷自动机确定的有穷自动机DFA的表示的表示 3.2.1 状态转换图状态转换图 设设DFA有有m个状态，个状态，n个输入字符，那么这个图含有个输入字符，那么这个图含有m个状态结点，每个结点最多有个状态结点，每个结点最多有n条箭弧射出和别的结点相连条箭弧射出和别的结点相连接，每条弧用接，每条弧用中的一个不同输入符号作记号。整个图含有中的一个不同输入符号作记号。整个图含有唯一的一个初态和若干个（可以唯一的一个初态和若干个（可以0个）终态结。个）终态结。 习惯上，初态结可以用习惯上，初态结可以用“=

9、”或或“”表示，终态结表示，终态结用双圆圈表示或标以用双圆圈表示或标以“+”。对。对t(q,a)=q指从状态结指从状态结q到状到状态结态结q画标记画标记a的弧。的弧。10 例例题：题：DFA M=(0, 1, 2, 3，a, b，t，0，3)，其中，其中t定义为：定义为： t(0,a)=1， t(0,b)=2， t(1,a)=3， t(1,b)=2， t(2,a)=1， t(2,b)=3， t(3,a)=3， t(3,b)=3解：该解：该DFA M的状态图：的状态图：0123abbaaba, b11确定的有穷自动机确定的有穷自动机DFA的表示（续）的表示（续）3.2.2 状态转换矩阵状态转换矩

10、阵 矩阵的行表示状态，列表示输入字符，矩矩阵的行表示状态，列表示输入字符，矩阵元素表示相应的状态行在输入字符列下的新阵元素表示相应的状态行在输入字符列下的新的状态，即的状态，即t(k,a)的值。的值。12例（题同）例（题同）解：该解：该DFA M的矩阵表示的矩阵表示状态状态 字符字符ab0121322133330123abbaaba, b t(0,a)=1， t(0,b)=2， t(1,a)=3， t(1,b)=2， t(2,a)=1， t(2,b)=3， t(3,a)=3， t(3,b)=3133.2.3 有关自动机术语有关自动机术语(1)道路：对于道路：对于*中的任何符号串中的任何符号串，

11、若存在一条从初态到，若存在一条从初态到某终态的路径。某终态的路径。(2)识别：道路上所有弧的标记连接成的符号串等于识别：道路上所有弧的标记连接成的符号串等于，则，则称称可为可为DFA M所识别（所接受）。所识别（所接受）。即若即若 *, t(q,)=P，其中，其中q为为DFA M的初始状态，的初始状态，PF（终态集）。（终态集）。若若M的初态结同时也是终态结，则空字的初态结同时也是终态结，则空字可为可为M所识别，所识别，即即qF, f(q, )=q(3)运行：运行： t(q, 1 2) = t(t(q, 1), 2)，其中，其中qQ， 1 2为输为输入字符串，且入字符串，且 1 ， 1 2 *

12、14例例解：解：t(0, abba) = t(t(0,a), bba)= t(1, bba) = t(t(1,b), ba) = t(2, ba) = t(t(2,b), a) = t(3, a) = 3 得证得证题：试证题：试证abba可为例可为例1的的DFA M所识别（所接受）。所识别（所接受）。0123abbaaba, b15 3.2.4 有关确定有穷自动机的结论有关确定有穷自动机的结论 把把DFA M所能接受的所有符号串（符号串的所能接受的所有符号串（符号串的全体）记为全体）记为L(M)。 上的一个字集上的一个字集V*是正规的，当且仅当存是正规的，当且仅当存在一个在一个上的确定有穷自动

13、机上的确定有穷自动机M，使得，使得L(M)=V。16有限自动机识别的语言有限自动机识别的语言 例子例子 例：下图中的自动机所能识别的语言是什么？例：下图中的自动机所能识别的语言是什么？q0q2q1q3abbaba17 定义定义3.4 一个不确定的有穷自动机一个不确定的有穷自动机NFA N也是一个五元组：也是一个五元组：M = ( Q, , t, q0, F ) (1)Q是一个有穷集合，它的每一个元素称为一个状态；是一个有穷集合，它的每一个元素称为一个状态； (2)是一个有穷字母表，它的每一个元素称为一个输入字符；是一个有穷字母表，它的每一个元素称为一个输入字符； 也称为输入符号字母表也称为输入

14、符号字母表 (3) t是一个是一个Q*到到Q的子集的映射：的子集的映射： t : Q*2Q (4)q0是是Q的子集，是非空的初态集；的子集，是非空的初态集； (5)F是是Q的子集，是一个终态集，也称可接收状态或结束状态。的子集，是一个终态集，也称可接收状态或结束状态。3.2.5 不确定的有穷自动机不确定的有穷自动机(NFA)的定义的定义18NFA的表示用状态转换图（用状态转换图（ t是多值函数）是多值函数） 由由NFA的定义，可把一个含有的定义，可把一个含有m个状态和个状态和n个输入字符的个输入字符的NFA表示如下：表示如下：图中有图中有m个状态节，对每个状态节可射出若干条弧和别个状态节，对每

15、个状态节可射出若干条弧和别的状态节相连，且每条弧用的状态节相连，且每条弧用*中的一个字（不一定要不中的一个字（不一定要不同的字且可以是空字同的字且可以是空字）作标记（或称输入字）。整个）作标记（或称输入字）。整个图中至少含有一个初态节以及若干个（可以是图中至少含有一个初态节以及若干个（可以是0个）终个）终态节。态节。 某些节既可以是初态节也可以是终态节。某些节既可以是初态节也可以是终态节。19例例题：一个题：一个NFA M(q0, q1，0, 1，t，q0，q1)，其中，其中 t(q0, 0)=q0, q1, t(q0, 1)=q1, t(q1, 0)=, t(q1, 1)=q0, q1,解：

16、其状态图如下：解：其状态图如下：q00q1011120例例如下状态图也是一个如下状态图也是一个NFA0a,b1aabba,b2a,b21有关非确定有穷自动机的术语有关非确定有穷自动机的术语对于对于*中的任何一个串中的任何一个串t可被可被NFA M识别是指：识别是指：若对这个字（串）若对这个字（串）t存在一条从某个初态节到某一存在一条从某个初态节到某一个终态节的道路，且这条道路上所有弧的标记字依个终态节的道路，且这条道路上所有弧的标记字依序连接起来的字符串（不理睬那些标记为序连接起来的字符串（不理睬那些标记为的弧）的弧）等于等于t，则，则t可识别（或可接受）可识别（或可接受）若若M的某些节点既是

17、初态节也是终态节，或存的某些节点既是初态节也是终态节，或存在一条从某个初态节到某个终态节的在一条从某个初态节到某个终态节的道路，则空道路，则空字字可为可为M所识别（所接受）。所识别（所接受）。22NFA和和DFA的关系的关系 DFA是是NFA的一个特例。的一个特例。 对于每个对于每个NFA M，存在一个，存在一个DFA M，使得，使得L(M)=L(M) 对于任何两个有穷自动机对于任何两个有穷自动机M和和M，如，如L(M)=L(M)则则称称M和和M是是等价等价的。的。 如果如果M仅通过重新标记它的状态，就能转换成仅通过重新标记它的状态，就能转换成M，则，则M和和M称为同构的。称为同构的。 对于每

18、一个对于每一个NFA M，存在一个等价的、具有最少状态个，存在一个等价的、具有最少状态个数的数的DFA M，对于其它的，对于其它的DFA M”，若，若M”的状态个数的状态个数与与M相同且等价于相同且等价于M，则必然有，则必然有M”与与M同构，即：同构，即：M在结构上是唯一的。在结构上是唯一的。23243.3 NFA DFA的转换（的转换（NFA的确定化）的确定化） 通过以下步骤，可以将一个通过以下步骤，可以将一个NFA转换为等价的转换为等价的DFA：1.寻找并消除空移环路；寻找并消除空移环路；2.消除余下的空移；消除余下的空移；3.确定化确定化 子集法、造表法；子集法、造表法；4.DFA的最小

19、化的最小化构造状态集合的划分构造状态集合的划分25 3.3.1 NFA中空移环路的寻找和消除中空移环路的寻找和消除空移环路：空移环路：一个空移环路，是一个从状态一个空移环路，是一个从状态A开始，并以状态开始，并以状态A结结束的空移动序列。束的空移动序列。q1q2q1q2q3q1q2q3qn消除方法：消除方法：合并环路上的合并环路上的节点为新节点。节点为新节点。若含初态，则若含初态，则新节点为初态。新节点为初态。若含终态，则若含终态，则新节点为终态。新节点为终态。课本课本P53 例例3.426 3.3.2 NFA的消除空移ABa1q1q2qna2anABa1q1q2qna2ana1ana2消除方

20、法：消除方法：删除删除弧，产生新弧。弧，产生新弧。若若A为初态，则为初态，则B结点也为初态。结点也为初态。若若B为终态，则为终态，则A结点也为终态。结点也为终态。273.3.3 利用状态转换表消除空移1. 首先找出直接经由一个空移到达某个终态的所有状态。每找到这样一个状态，标记为终态。2. 然后，考虑消除与未被标记为终态的那些状态相关的空移。3. 对表中每一个具有射出连线的状态继续按上述方式处理，直到状态表不再变动为止。4. 从表中删除列和没有任何元素的空行，便得到一个不含空移的状态转换表。28+-.dSAAAAB,CEBBFCDCDDFEGEFGHHHF表3.2 图3.4中NDFA标记状态后

21、的情况29+-.dSAAGB,C,EAGB,C,EBBCDCDDEGEGHHH表3.3 删除空移后的状态转换图303.3.4 NFA的确定化子集法 一个例子一个例子( 无空移无空移) p55 图图3.9 介绍一种称介绍一种称子集法子集法的算法来将的算法来将NFA转换成接转换成接收同样语言的收同样语言的DFA。 算法的基本思想是：把算法的基本思想是：把DFA中的每一个状态中的每一个状态对应对应NFA中的一组状态。即由于中的一组状态。即由于NFA中的中的t是多值是多值的，所以在读入一个输入符号后可能达到的状态的，所以在读入一个输入符号后可能达到的状态是集合，而子集法就是用是集合，而子集法就是用DF

22、A的状态记录该状态的状态记录该状态的集合。的集合。31将NDFA M=(Q, ,t,Q0,F) 转换为DFA M=(Q, ,t,q0,F)的步骤： 1. M的状态集Q是由M的状态集Q的所有子集组成的。用p1,p2, ,pi表示Q的元素。2. 若p是M的一个终态，则M中的每一个包含p的状态,p,都是M的一个终态。3. 若S=S1,S2,Sj是M的初态，则S=S1,S2,Sj是M的初态。4. 令p1,p2,pn是M中的一个状态，其中p1,p2,pn是M中的状态。对某个输入符号a，考虑M中的转换函数：t(p1,a), t(p2,a), , t(pn,a)，按以下方法得到M的转换函数t: a. 令t(

23、p1,a)U t(p2,a)UU t(pn,a)=q1,q2,qr b. 置t(p1,p2,pn,a)=q1,q2,qr5. 对M每一状态和每个输入符号a，重复步骤4.32利用状态表将NDFA转换为DFA。以表3.3为例+-.dSAAGB,C,EAGB,C,EBBCDCDDEGEGHHHB,C,ED,GB,C,E新状态新状态D,GD,H新状态新状态D,HD,H新状态新状态333.3.5 确定化确定化-造表法造表法（2）Move(I, a)状态集合状态集合I的的a弧转换弧转换 假定假定I是状态集的一个子集，是状态集的一个子集，a是是中的一个字符，定义中的一个字符，定义 Ia _closure(J

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

25、状态图如下：1526a4a73a8假定假定 I= _closure(1)1, 2从状态集从状态集I出发经过一条出发经过一条a弧而能到达的状态结全体弧而能到达的状态结全体J为为5, 3, 4；而而_closure(J) =5, 6, 2, 3, 8, 4, 7例例35NFA的确定化的确定化 从从NFA N (Q, , t, q0, F)构造一个构造一个DFA M (Q, , t, q0, F)，其中，其中 (1) Q是由是由Q一些子集组成；一些子集组成； (2) M与与N的输入字母表相同，都是的输入字母表相同，都是； (3)t定义：定义： t(q1, q2, qj, a)=q1, q2, qi，

26、其中，其中 _closure(move(q1, q2, qj, a)= q1, q2, qi (4) q0 = _closure(q0)为为M的开始符号（初态）；的开始符号（初态）； (5) F =qj, qk, qe，其中，其中qj, qk, qe Q且且qj, qk, qeF 36具体过程具体过程为了方便起见，令为了方便起见，令中只有中只有a,b两个字母，即两个字母，即a, b（1）构造一张表，此表的每一行有三列，第一列为）构造一张表，此表的每一行有三列，第一列为I，第二，第二列为列为Ia，第二列为，第二列为Ib。即。即I IIaIb_closure(q0)首先置该表的第一列为首先置该表的

27、第一列为_closure(q0)。（2）一般而言，若某一行的第一列的状态子集已确定，例如）一般而言，若某一行的第一列的状态子集已确定，例如记为记为I，则可以求出，则可以求出Ia和和Ib ；37具体过程（续）具体过程（续） （3）检查）检查Ia和和Ib是否已在表的第一列中出现，把未曾出现者是否已在表的第一列中出现，把未曾出现者填入到后面空行的第一列位置上。填入到后面空行的第一列位置上。 （4）对未重复）对未重复Ia 、 Ib的新行重复上述过程的新行重复上述过程(2)、(3) ，直到所，直到所有第二列和第三列的子集全部在第一列中出现；有第二列和第三列的子集全部在第一列中出现； 上述过程必定在有限步

28、内终止，因为上述过程必定在有限步内终止，因为N的状态子集的个数的状态子集的个数是有限的。我们也可将表看成状态转换矩阵，即把其中每个是有限的。我们也可将表看成状态转换矩阵，即把其中每个子集看成一个状态，就可以由这张表唯一刻划出一个确定的子集看成一个状态，就可以由这张表唯一刻划出一个确定的有穷自动机有穷自动机DFA。其初态就是该表的第一行第一列的。其初态就是该表的第一行第一列的_closure(q0) ，终态就是那些含有，终态就是那些含有F的子集。的子集。38例例题：将下图题：将下图NFA N确定化。确定化。12b3a7045b68a910bIIaIbSab0,1,2,4,71,2,3,4,6,7

29、,81,2,4,5,6,70121,2,3,4,6,7,8 1,2,3,4,6,7,8 1,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,9 1,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)构造转换矩阵构造转换矩阵39 接上页接上页(2)对表中所有的子集重新命名，其中对表中所有的子集重新命名，其中0是初态，是初态，4是终态。是终态。 对应的对应的DFA M：0124ba3aabbabab40例例题：将下图确

30、定化：题：将下图确定化：解：解：(1)构造转换矩阵构造转换矩阵II0I1S01s,x,yws,x,yABAw y,s,x,zBCs,x,y,zw,s,x,ys,x,yCDAw,s,x,yws,x,y,zDBCsyxwz1010141接上页接上页 DFA M为：为：ABDC011010142例子3.7：求与右图等价的DFA= (Q,t,q0,F) 1. =x,y2. Q=q0,q1,q2,q3,q0,q1,q0,q1,q2,q33. F=q3,q0,q3,q1,q3,q2,q3,q0,q1,q2,q3xyq0q1, q2q0q1, q2q0, q3q1, q2, q3q0, q3q1, q2,

31、q3q0, q3q1, q2, q3q0, q1, q3q1, q2, q3q0, q1, q3q0, q1,q2, q3q0, q1,q2, q3q0, q1,q2, q3q0, q1,q2, q3q0, q1,q2, q3. 确定化后的状态转换矩阵确定化后的状态转换矩阵xyq0q1q0q1q2q3q2q3q2q3q4q3q4q5q5q5q5q5433.3.6 消除不可达状态 有穷自动机的有穷自动机的多余状态多余状态：是指这样的状态，从该自动：是指这样的状态，从该自动机的开始状态出发，任何输入串也不能达到的那个状态。机的开始状态出发，任何输入串也不能达到的那个状态。 01S0S1S5S1S2

32、S7S2S2S5S3S5S7S4S5S6S5S3S1S6S8S0S7S0S1S8S3S6443.3.7 DFA的化简的化简 对已求得的对已求得的DFA，可以进一步将其化简，即求最小，可以进一步将其化简，即求最小DFA。也就是对于任意给定的也就是对于任意给定的DFA M构造另一个构造另一个DFA M，使，使L(M)=L(M)，且，且DFA M的状态个数少于的状态个数少于DFA M的状态个的状态个数。数。 消除多余状态消除多余状态 DFA M状态最少化的过程：状态最少化的过程： 把把M的状态集分割成一些不相交的子集，使得任何不同的状态集分割成一些不相交的子集，使得任何不同的两个子集的状态都是可区别

33、的，而同一子集中的任何两个的两个子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的。状态都是等价的。45有关分割法所用的概念有关分割法所用的概念定义定义3.7 等价等价 设设s,t是是M的两个不同的状态，的两个不同的状态，s,t等价的意思是：如果从状等价的意思是：如果从状态态s出发能读出某个字出发能读出某个字而停于终态，那么同样从而停于终态，那么同样从t出发也能读出发也能读出同一个字出同一个字而停于终态；反之，若能从而停于终态；反之，若能从t出发读出某个字出发读出某个字而而停于终态，那么同样从停于终态，那么同样从s出发也能读出字出发也能读出字而停于终态。而停于终态。 等价的条件：等价

34、的条件：(1)一致性条件一致性条件 状态状态t,s必须同时是可接受状态或不可接受状态；必须同时是可接受状态或不可接受状态；(2)蔓延性条件蔓延性条件 对于所有输入符号，状态对于所有输入符号，状态s和状态和状态t必须转换到必须转换到等价的状态里等价的状态里(注：状态注：状态s对应有输入对应有输入a而状态而状态t无输入无输入a时，这两个时，这两个状态是不等价的）状态是不等价的）。46有关分割法所用的概念有关分割法所用的概念定义定义3.8 可区分可区分 若若DFA M中的两个状态中的两个状态s,t不等价，则这两个状态是可区别的。不等价，则这两个状态是可区别的。例如：终态和非终态是可区别的（读出例如：

35、终态和非终态是可区别的（读出）；）； 下图中的状态下图中的状态2与状态与状态3（读出（读出b字）；字）； 0124ba3aabbabab47分割法分割法(1)把把Q的终态和非终态分开，分成两个子集的终态和非终态分开，分成两个子集 终态组和非终态组和非终态组，形成基本分划终态组，形成基本分划；显然，属于这两个不同子集的状态；显然，属于这两个不同子集的状态是可区别的。是可区别的。(2)假定到某个时候假定到某个时候含有含有m个子集，记个子集，记=I(1), I(2), , I(m)，若存在一个输入字符若存在一个输入字符a使得使得Ia( i )不全包含在现行不全包含在现行的某个子集的某个子集I( j

36、)中，就将中，就将I( j )一分为二；至此把一分为二；至此把I( i )分成两半，形成新的划分成两半，形成新的划分分 new。48分割法（续）分割法（续） (3)重复上述过程重复上述过程(2)，直到，直到所含的子集不再增长为止，此所含的子集不再增长为止，此时得到最后的划分时得到最后的划分 finish；此时，此时， 中的所有子集已是不可再分的了。也就是说，同中的所有子集已是不可再分的了。也就是说，同个子集中的状态都是互相等价的，而不同子集中的状态则个子集中的状态都是互相等价的，而不同子集中的状态则是可区别的。是可区别的。 (4)对于对于 finish中的每一个子集，选取子集中的一个状态代中的

37、每一个子集，选取子集中的一个状态代表其它状态，这个代表就是化简了的表其它状态，这个代表就是化简了的DFA M的状态。的状态。例如：假定例如：假定I=S1, S2, S3这样一个子集，则可选这样一个子集，则可选S1代表这个代表这个子集，那么在原自动机中，凡导入到子集，那么在原自动机中，凡导入到S2, S3的弧都导入到的弧都导入到S1,然后把然后把S2, S3结点从原来的状态集合中删除，因为它们已成结点从原来的状态集合中删除，因为它们已成了一些多余的状态（从开始状态出发，任何输入串也不能了一些多余的状态（从开始状态出发，任何输入串也不能达到的状态）。达到的状态）。49对划分的说明对划分的说明例如：

38、假定例如：假定I( i )中的状态中的状态S1和和S2经经a弧分别到达状态弧分别到达状态t1和和t2，而而t1和和t2属于现行属于现行中的两个不同子集，则将中的两个不同子集，则将一分为二，一分为二，使得一半含有使得一半含有S1 ： I( i1 ) =S | S I( i1 )且且S经经a弧到达弧到达t1，则另一半含有则另一半含有S2 ： I( i2 ) = I( i ) I( i1);由于由于t1和和t2是可区别的，即存在一个字是可区别的，即存在一个字， t1将读出将读出而停于而停于终态，而终态，而t2或读不出字或读不出字或虽可读出字或虽可读出字但不到达终态，但不到达终态，或情况恰好相反。因而

39、字或情况恰好相反。因而字将将S1和和S2区别开来，也就是说，区别开来，也就是说， I( i1 )和和I( i2 )中的状态是可区别中的状态是可区别50若若I中含有原来的初态，则中含有原来的初态，则S1是是新初态新初态；若；若含有原来的终态，则含有原来的终态，则S1是是新终态新终态。 经过消除多余状态和合并等价状态而得到经过消除多余状态和合并等价状态而得到的的DFA M，便是最简化的（包含最少状态的），便是最简化的（包含最少状态的）DFA。化简后初态和终态的确定化简后初态和终态的确定51a134267=5aaaaaabbbbbbb例：化简下图中的例：化简下图中的DFA解：解：(1)把把M的状态分

40、成两组：的状态分成两组：1,2,3,4、5,6,7；52例：例：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=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 化简了的

41、化简了的DFA M为：为：53例：化简后的例：化简后的DFA化简后的化简后的DFAaa1346=5aabbbbba54例例思考题：将下列DFA M最小化。0124ba3aabbabab解：整个划分为：解：整个划分为：0,2、1 、3、4104a3abbabab0,1,2,34b:0,2,1,3,455例例将下图将下图DFA最小化。最小化。解：解：(1)把把M的状态分成两组：终结组的状态分成两组：终结组C、非终结组、非终结组A,B,D； (2)考虑考虑A,B,D，由于，由于A,B,D1=A,C，因此对，因此对A,B,D一分为一分为二，分成二，分成A、B,DABDC0110101ABC011010

42、56 例例(续续)至此，整个集合含有三组：至此，整个集合含有三组：A、B,D、C。最后，令状态最后，令状态B代表代表B,D，将原来导入到，将原来导入到D的弧都导入到的弧都导入到B，并删，并删除除D。这样，所得的化简。这样，所得的化简DFA M为：为：ABC011010原因：B,D0 时B无出边，D有出边，不满足蔓延性条件正确的划分：A、B、C、D57例例化简如下化简如下DFA M1401101002037500161100解：整个划分为：解：整个划分为：0,1、2,5、3、4,7、6，用，用0,1,2,3,4分布分布代替子集代替子集0,1、2,5、3、4,7、6001210043110058

43、3.4 正规文法和有穷自动机间的转换正规文法和有穷自动机间的转换3.4.1 (1)正规文法正规文法GNFA M：构造规则构造规则： (a) 与与G中的中的VT相同；相同； (b) M中的中的Q与与G中的中的VN相同，即文法相同，即文法G中的每个非终结符中的每个非终结符生成自动机生成自动机M中的一个状态，中的一个状态，G的开始符号的开始符号S是是M的初态的初态；增增加一个新的状态加一个新的状态Z，作为接受状态，作为接受状态。 (c) 对产生式对产生式UaV，其中，其中a VT或或，U,VVN，构造，构造M的一个转换函数的一个转换函数t(U,a)=V； (d) 对产生式对产生式Ua，构造，构造M的

44、转换函数的转换函数t(U,a)=Z（终态（终态集）。集）。59正规文法正规文法GNFA M 例3.10 课本P69构造正规文法构造正规文法GS等价的等价的NFA M。 GS: S+N S-N Sd N Sd NdN Nd解：与文法解：与文法G等价的等价的NFA M如下图：如下图：SNF+d-ddt(S,+)=Nt(S,d)=Ft(S,-)=Nt(N,+d=Nt(S,d)=Nt(N,d)=Fd60正规文法正规文法GNFA M 例2构造正规文法构造正规文法GS等价的等价的NFA M。 GS: SaA SbB Sb AaB AbA BaS BbA B解：与文法解：与文法G等价的等价的NFA M如下图

45、：如下图：SaZABbbabab613.4.1 左线性文法左线性文法-NFA M 转换规则转换规则： (a) 文法的开始符号文法的开始符号S是是M的终态。的终态。 (b) 引入一个新的非终结符引入一个新的非终结符R作为初态结点。作为初态结点。 (c) 对于文法中的每一个形如对于文法中的每一个形如U-a的产生式，从初态的产生式，从初态结点画一条弧到结点结点画一条弧到结点U，且用，且用a标记该弧线。标记该弧线。 (d) 对于文法中的每一个形如对于文法中的每一个形如U-Va的产生式，从结的产生式，从结点点V画一条弧到结点画一条弧到结点U，且用，且用a标记该弧线。标记该弧线。623.4.1 左线性文法

46、左线性文法-NFA M 例例：GS: S-S1 S-A1 A-A0 A-0 RAS0011633.4.2 NFA M 正规文法正规文法G 转换规则转换规则： (a) 对转换函数对转换函数t(U,a)=V，写成产生式，写成产生式UaV； (b) 对终态对终态Z，增加产生式，增加产生式Z； (c) VN为为NFA所有状态中的标记（所有状态中的标记（Q），），VT为为NFA的的， NFA的初态就是开始符号的初态就是开始符号S。64例例例：给出与例：给出与NFA等价的正规文法等价的正规文法GAaDBbbaabCb解：与解：与NFA等价正规文法等价正规文法G=(VN, VT, P, S)=(A,B,C,

47、D,a,b, P, A)，其中其中P为：为： AaB AbD BbC CaA CbD C DaB DbD D 653.5 正规表达式与正规表达式与FA单词的描述工具：正规文法单词的描述工具：正规文法正规文法（正规文法（3型文法）的形式定义型文法）的形式定义 设设G=( VN, VT, P, S)为一文法，若为一文法，若G的任何产的任何产生式生式A 或或A B ，其中，其中A、B VN ， VT* 。66 正规文法的例子正规文法的例子例：例：“无符号实数无符号实数”定义定义 d | . | e d | . | e | d e | d | d | s d d | 其中其中s 正负符号正负符号+、6

48、73.5.1 单词的描述工具单词的描述工具正规式的定义正规式的定义正规式也叫正则表达式，用于描述称为正规集的语言。正规式也叫正则表达式，用于描述称为正规集的语言。定义定义3.9 字母表字母表上的正规式和正规集的递归定义为：上的正规式和正规集的递归定义为：(1)和和是是上的正规式，它们所代表的正规集为上的正规式，它们所代表的正规集为 ()；(2)任何任何a，a是是上的一个正规式，它所表示的正规集为上的一个正规式，它所表示的正规集为a；(3)假定假定e1与与e2都是都是上的正规式，它们所表示的正规集为上的正规式，它们所表示的正规集为L(e1)和和L(e2)，那么，那么(e1)、 e1| e2、 e

49、1 e2和和e1*也是正规式，它们所表示也是正规式，它们所表示的正规集分别为的正规集分别为 L(e1)、L(e1)L(e2)、 L(e1) L(e2)、 (L(e1) * (4)仅用有限次使用上述三步骤而定义的表达式方是仅用有限次使用上述三步骤而定义的表达式方是上的正规上的正规式，仅有这些正规式所表示的字集才是式，仅有这些正规式所表示的字集才是上的正规集。上的正规集。68正规式正规式运算符优先关系运算符优先关系 |(或或) (连接连接) 正规文法正规文法将将上的一个正规式上的一个正规式r，转换为正规文法，转换为正规文法G=( VN, VT, P, S).1.令令VT= 2. S-r , S为开

50、始符号为开始符号3. 若若x和和y都是正规式，则都是正规式，则 产生式产生式 重写为：重写为：r1. A-xy A-xB B-yr2. A-x*yA-xA A-y r3. A-x|y A-x A-yl不断做变换，直到每个产生式右端最多只含一个不断做变换，直到每个产生式右端最多只含一个VN 883.5.6 正规式正规式-正规文法正规文法l例例 将正规式将正规式R=a(a d) 转换为相应的正规文法。转换为相应的正规文法。 VT=a,d Sa(a d) r3. SaA AaAAdA A VN=S,Ar1. SaA A(a d) r2. A(a d)A A893.5.6 正规文法正规文法-正规式正规

51、式对对G= ( VN, VT, P, S), 存在一个存在一个 = VT上的正规式上的正规式e，使得，使得 L(R)=L(e) 。在此介绍在此介绍2种转换方法：种转换方法：一：一：1.令令 =VT2.转换规则转换规则 文法产生式文法产生式正规式正规式AxB ByA=xy AxA y A=x y Ax y A=x yl不断做变换，直到只剩下一个不断做变换，直到只剩下一个开始符号开始符号定义的产定义的产生式，且该产生式生式，且该产生式右端不含右端不含VN 903.5.6 正规文法正规文法-正规式正规式 例子例子例例 文法文法Gs:SaA AaA AdA Sa Aa Ad S=a(a d) (a d

52、) a =a(a d) (a d) =a(a d) ) 所以，所以，t=a(a d) 解答：解答： SaA a AaA a dA d A(a d)A (a d) A(a d) (a d)913.5.6 正规文法正规文法-正规式正规式二二.方程组求解法方程组求解法 p78 例例3.19 S-0A|1B|0|1 A-0S|1B|1 B-1S+0A解：写出关于变量解：写出关于变量S、A、B的正规方程组：的正规方程组： S=(0+1)+0A+1B (1) A=1+0S+1B (2) B=1S+0A (3)将将(3)代入代入(1)和和(2), 可得：可得： S=(0+1)+0A+1(1s+0A)=(0+

53、1)+(0+10)A+11S (6) A=1+0S+1(1S+0A)=1+10A+(0+11)S (7) 将将(7)重写为重写为A=aA+b的形式：的形式： A=10A+(1+(0+11)S) 则则A=(10)*(1+(0+11)S) 将将A代入代入(6), 得得S=0+1+(0+10)10*(1+(0+11)S)+11S S=(0+10)(10*)(0+11)+11)S+(0+10)(10*)1+0+1) 则：则： S= (0+10)(10*)(0+11)+11)* (0+10)(10*)1+0+1)92 3.6 DFA在计算机中的表示在计算机中的表示要在计算机中表示一个要在计算机中表示一个

54、DFA，只需表示它的映射，只需表示它的映射3.6.1 矩阵表示法矩阵表示法 例例3.21 映射映射t(q0,x1)=q1, t(q0,x2)=q3, t(q1,x1)=q2, t(q1,x2)=q0, t(q2,x1)=q3, t(q2,x2)=q2. 定义二维数组定义二维数组M=1,3, 2,0,3,2 x1X2q0q1q3q1q2q0q2q3q1q3q0q2933.6.2 表结构表结构l 在表结构中，每一个状态对应一个表，表中包括在表结构中，每一个状态对应一个表，表中包括状态名，从该状态发出的弧数、每条弧上的标记状态名，从该状态发出的弧数、每条弧上的标记（输入字母）以及弧达到状态所在表的首

55、地址。（输入字母）以及弧达到状态所在表的首地址。l 例例3.22 p81943.6.3 自动机的编程实现自动机的编程实现 p820: if IS-Digit(T) then goto 2 else if (T=+) or (T=-) then goto 1 else if (T=.) then goto 3 else Error;1: if IS-Digit(T) then goto 2 else if (T=.) then goto 3 else Error;2: if IS-Digit(T) then goto 2 else if (T=.) then goto 4 else goto 5;3: if IS-Digit(T) then goto 4 else Error4: if IS-Digit(T) then goto 4 else Error5: halt 1d+-.0324dd.dd95第三章作业第三章作业 p83-