编译原理重点

编译原理重点第1页，共117页，2023年，2月20日，星期四有穷自动机

有穷自动机（或有限自动机）作为一种识别工具，它能正确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合。引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。分类：确定的有穷自动机（DFA）不确定的有穷自动机（NFA）第2页，共117页，2023年，2月20日，星期四3.1概述有穷自动机（FA）有穷自动机（FA，FiniteAutomata）是一种有限离散数字系统的抽象数学模型。这个系统具有有限数目的内部“状态”。所谓状态，是可以将事物区分开的一种标识。例如：数字电路（0，1），十字路口的红绿灯等都是离散状态系统，其状态数目是有限的。连续状态系统则如水库的水位、室内温度变化等。电梯的控制机制，不需要保存所有以前的服务要求，仅需记住当前的层次、运动的方向以及未满足的服务要求。文本编辑程序和词法分析程序是有限状态系统，计算机本身和人的大脑也可看成有限状态系统。第3页，共117页，2023年，2月20日，星期四例过河问题题目一个人带着一头狼、一头羊以及一棵青菜，处于河的左岸，需要渡到河的右岸。有一条小船，每次只能携带人和其余的三者之一。不能让狼和羊单独在一起，无论在左岸还是右岸，否则狼会吃掉羊。同样，也不能让羊和青菜单独一起。如何才能安全渡过河呢？第4页，共117页，2023年，2月20日，星期四例过河问题分析观察每次摆渡后河两岸的局势，使问题模型化。人（M），狼（W），羊（G），菜（C）。存在有16种子集，用连字号”-”连接子集的对偶表示状态，例如：

MG-WC，表示：人和羊在左岸，狼和菜在右岸。

16种状态中的某些状态，是不应该引入系统的，例如GC-MW，有关死活。人所进行的摆渡活动，可作为系统的输入。人可单独过河（输入为M），带着狼过河（输入为W），带着羊过河（输入为G）或者是带着菜过河（输入为C）。

问题：初始状态应该是什么？终止状态应该是什么？第5页，共117页，2023年，2月20日，星期四例过河问题分析（续）初始状态：MWGC-φ；终止状态：φ-MWGC。MWGC-φWC-MGg问题：第6页，共117页，2023年，2月20日，星期四例过河问题状态转换图MWGC-φWC-MGC-MWGMWG-CMGC-WG-MWCMG-WCφ-MWGCW-MGCMWC-Gggggmggggmmmccccwwww起始第7页，共117页，2023年，2月20日，星期四有穷自动机（FA）数字系统：可以从一个状态移动到另一个状态；每次状态转换，都上由当前状态及一组输入符号确定的；可以输出某些离散的值集。

FA：一个状态集合；状态间的转换规则；通过读头来扫描的一个输入符号串。读头：从左到右扫描符号串。移动（扫描）是由状态转换规则来决定的。第8页，共117页，2023年，2月20日，星期四ddd;.dd+;输入符号串一个FA的例子读头数字A数字+-.SGBH数字数字..数字接收：若扫描完输入串，且在一个终止状态上结束。阻塞：若扫描结束但未停止在终止状态上；或者为能扫描完输入串（如遇不合法符号）。不完全描述：某些状态对于某些输入符号不存在转换。练习：+34.567.1233.4.5第9页，共117页，2023年，2月20日，星期四=80;0134256eniL字母字母字母字母数字数字数字==；；0124563Line=80;id,‘Line’=,num,‘80’;,数字数字字母字母11==0003;;1输入符号串输出有限控制器读头第10页，共117页，2023年，2月20日，星期四3.2有穷自动机的形式定义DFA:DeterministicFiniteAutomataNFA:NondeterministicFiniteAutomataDFA的定义定义3.1一个确定的有穷自动机(DFA)M是一个五元组：

M=(K,Σ,f,S,Z)(1)K是一个非空有穷集合，它的每一个元素称为一个状态；

(2)Σ是一个有穷字母表，它的每一个元素称为一个输入字符；Σ也称为输入符号字母表第11页，共117页，2023年，2月20日，星期四确定的有穷自动机DFA的定义（续）

(3)f是从Σ×K到K的单值部分映射；

f(ki,a)=kj，其中ki∈K，kj∈K

说明：当前状态为ki

，输入字符a时，将转换到下一个状态kj

，把kj称为ki的一个后继状态。

DFA的确定性就表现在f是单值函数，即对任意状态k∈K，输入符号a∈Σ，f(k,a)唯一确定一个状态。

(4)S∈K，是唯一的初态；

(5)Z是K的子集，是一个终态集，终态也称为可接收状态或结束状态。第12页，共117页，2023年，2月20日，星期四确定的有穷自动机DFA的表示

3.2.1状态转换图设DFA有m个状态，n个输入字符，那么这个图含有m个状态结，每个结点最多有n条箭弧射出和别的结点相连接，每条弧用Σ中的一个不同输入符号作记号。整个图含有唯一的一个初态和若干个（可以0个）终态结。习惯上，初态结可以用“=>”或“－>”表示，终态结用双圆圈表示或标以“+”。对f(ki,a)=kj指从状态结ki到状态结kj画标记a的弧。第13页，共117页，2023年，2月20日，星期四

例１题：DFAM=({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解：该DFAM的状态图：0123abbaaba,b第14页，共117页，2023年，2月20日，星期四确定的有穷自动机DFA的表示（续）3.2.2状态转换矩阵矩阵的行表示状态，列表示输入字符，矩阵元素表示相应的状态行在输入字符列下的新的状态，即f(k,a)的值。第15页，共117页，2023年，2月20日，星期四例２（题同１）解：该DFAM的矩阵表示状态字符ab0121322133330123abbaaba,b0001第16页，共117页，2023年，2月20日，星期四3.2.3有关自动机术语(1)道路：对于Σ*中的任何字α，若存在一条从初态到某终态的路径。(2)识别：道路上所有弧的标记连接成的字等于α，则称α可为DFAM所识别（所接受）。即若t∈Σ*,f(S,t)=P，其中S为DFAM的初始状态，P∈Z（终态集）。若M的初态结同时也是终态结，则空字ε可为M所识别，即Q∈K,f(Q,ε)=Q(3)运行：

f(Q,t1t2)=f(f(Q,t1),t2)，其中Q∈K，t1t2为输入字符串，且t1∈Σ，t1t2∈Σ*第17页，共117页，2023年，2月20日，星期四例３解：∵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的DFAM所识别（所接受）。0123abbaaba,b第18页，共117页，2023年，2月20日，星期四

3.2.4有关确定有穷自动机的结论把DFAM所能接受的所有字（字的全体）记为L(M)。

Σ上的一个字集V∈Σ*是正规的，当且仅当存在一个Σ上的确定有穷自动机M，使得L(M)=V。第19页，共117页，2023年，2月20日，星期四有限自动机识别的语言例子例：下图中的自动机所能识别的语言是什么？q0q2q1q3abbaba第20页，共117页，2023年，2月20日，星期四定义3.4

一个不确定的有穷自动机NFAN也是一个五元组：

M=(K,Σ,f,S,Z)(1)K是一个有穷集合，它的每一个元素称为一个状态；

(2)Σ是一个有穷字母表，它的每一个元素称为一个输入字符；Σ也称为输入符号字母表

(3)f是一个K×Σ*到K的子集的映射：

f:K×Σ*→2k

(4)S是K的子集，是非空的初态集；

(5)Z是K的子集，是一个终态集，也称可接收状态或结束状态。3.2.5不确定的有穷自动机(NFA)的定义第21页，共117页，2023年，2月20日，星期四NFA的表示

用状态转换图（∵f是多值函数）由NFA的定义，可把一个含有m个状态和n个输入字符的NFA表示如下：图中有m个状态结，对每个状态结可射出若干条弧和别的状态结相连，且每条弧用Σ*中的一个字（不一定要不同的字且可以是空字ε）作标记（或称输入字）。整个图中至少含有一个初态结以及若干个（可以是0个）终态结。某些结既可以是初态结也可以是终态结。第22页，共117页，2023年，2月20日，星期四例４题：一个NFAM＝({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第23页，共117页，2023年，2月20日，星期四例５如下状态图也是一个NFA0a,b1aabba,b2a,bε第24页，共117页，2023年，2月20日，星期四有关非确定有穷自动机的术语

对于Σ*中的任何一个串t可被NFAM识别是指：若对这个字（串）t存在一条从某个初态结到某一个终态结的道路，且这条道路上所有弧的标记字依序连接起来的字（不理睬那些标记为ε的弧）等于t，则t可识别（或可接受）若M的某些结点既是初态结也是终态结，或存在一条从某个初态结到某个终态结的ε道路，则空字ε可为M所识别（所接受）。第25页，共117页，2023年，2月20日，星期四补充：递归思想构造文法

在某些复杂的语言中，字符串可能包含一种结构，它递归地作为另一种（或者同一种）结构的一部分而出现，可利用递归思想来构造对应的文法。例1：定义语言L={ω|ω中a和b的个数相同}的文法。解：先构造出基础情况的文法：

S->ab|ba|ε再递归地构造出归纳情况的文法（新的生成式不能改变a和b的个数关系）：

S->Sab|aSb|abS|Sba|bSa|baS第26页，共117页，2023年，2月20日，星期四递归思想构造文法（续）

例1：求一个文法G，使得Ｌ(G)即该文法的语言是奇数个ａ和奇数个ｂ的组合。解：因为语言是奇数个ａ和奇数个ｂ的组合，所以打头的最小语言有四种组合：aabbabba

定义S和A，S是表示奇数个a和奇数个b的组合，而A是表示偶数个a和偶数个b的组合。 开始递归构造文法：

S->aaS|bbS|abA|baA…… A->aaA|bbA|abS|baS|ε……

第27页，共117页，2023年，2月20日，星期四补充：如何设计有限自动机 如同文法的设计，自动机的设计也是一个创造过程。有一种做法，在设计各种类型的自动机时都很有帮助，即采用一种心理上的技巧，把自己放在要设计的机器的位置上，考虑自己该如何实现自动机的任务。 假定自己是一台有限自动机，接受到一个输入符号串时，必须确定到目前为止所看到的字符串是否可为该自动机所识别。为了能够判断这一点，必须估算出识别时需要记住哪些关键的东西。 为什么不记住所有看到的东西呢？因为你是一台有限自动机，只有有限个状态，而这些状态是你记住事情的唯一办法。输入串可能很长，而你不可能记住所有的事情。 幸运的是，许多语言只需要记住某些关键的信息就可以了。第28页，共117页，2023年，2月20日，星期四设计有限自动机（续1）例1：构造一台有限自动机，识别所有由奇数个a和奇数个b组成的字符串。解：为了确定a和b的个数是否是奇数，不需要记住所看到的整个字符串，而只需要记住至此所看到的a、b个数是偶数还是奇数即可。一旦确定了关键信息，就可以开始设计状态了。 这些信息有如下四种可能性：第29页，共117页，2023年，2月20日，星期四设计有限自动机（续2）例1：(1)到此为止是偶数个a和偶数个b; (2)到此为止是奇数个a和偶数个b; (3)到此为止是偶数个a和奇数个b; (4)到此为止是奇数个a和奇数个b。 根据每种可能性设计一个状态，并根据可能的输入符号来设计状态之间的转移条件。1324aaaabbbb第30页，共117页，2023年，2月20日，星期四设计有限自动机（续3）例2：设计有限自动机M，识别含有00作为子串的所有{0，1}*上的字符串组成的语言。 如：0010，1001，110001001解：3种可能性：

(1)到此为止未看到模式“00”的任何符号; (2)到此为止看见了一个0; (3)到此为止已经看见整个模式“00”。第31页，共117页，2023年，2月20日，星期四设计有限自动机（续4）例2自动机的状态转换图为：qq0q0010,1100或者为（NFA）：qq0q000,10,100第32页，共117页，2023年，2月20日，星期四设计有限自动机（续5）例3构造一个有穷自动机M，识别所有形如0k的字符串，其中k是2或3的倍数。（2）识别0k的字符串，其中k是3的倍数：00000（1）识别0k的字符串，其中k是2的倍数：第33页，共117页，2023年，2月20日，星期四设计有限自动机（续6）例3的有穷自动机M为：sε00000ε00000以上两个自动机是否等价？这个自动机显示了ε转换的方便之处。第34页，共117页，2023年，2月20日，星期四设计有限自动机（续7）

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

1.思考题：构造一个有穷自动机M，识别{0，1，2}上的语言，该语言的每个字符串代表的十进制数能被3整除。

如：102，1020，10201，110,……思路(1):所有位数之和……；

(2):q0:3n+0q1:3n+1q2:3n+2q0+1->q1，因((3n+0)*10+1)/3余1；q1+1->q2，因((3n+1)*10+1)/3余2；….q0q1q2121201200第36页，共117页，2023年，2月20日，星期四NFA和DFA的关系

DFA是NFA的一个特例。对于每个NFAM，存在一个DFAM’，使得L(M)=L(M’)

对于任何两个有穷自动机M和M’，如L(M)=L(M’)则称M和M’是等价的。如果M仅通过重新标记它的状态，就能转换成M’，则M和M’称为同构的。对于每一个FAM，存在一个等价的、具有最少状态个数的FAM’，对于其它的FAM’’，若M’’的状态个数与M’相同且等价与M’，则必然有M’’与M’同构，即：M’在结构上是唯一的。第37页，共117页，2023年，2月20日，星期四3.3NFA→DFA的转换（NFA的确定化）通过以下步骤，可以将一个NFA转换为等价的DFA：1.寻找并消除空移环路；2.消除余下的空移；3.确定化。第38页，共117页，2023年，2月20日，星期四

3.3.1NFA中空移环路的寻找和消除空移环路： 一个空移环路，是一个从状态A开始，并以状态A结束的空移动序列。εq1q2εq1q2εq3εq1q2εq3εqnε……ε消除方法：合并环路上的结点为新结点。若含初态，则新结点为初态。若含终态，则新结点为终态。课本P56例3.4第39页，共117页，2023年，2月20日，星期四

3.3.2NFA的消除空移εABa1q1q2qna2an…εABa1q1q2qna2an…a1a2anεε消除方法：删除ε弧，产生新弧。若A为初态，则B结点也为初态。若B为终态，则A结点也为终态。第40页，共117页，2023年，2月20日，星期四3.3.4NFA的确定化——子集法

添加一个例子(无空移)

介绍一种称子集法的算法来将NFA转换成接收同样语言的DFA。算法的基本思想是：把DFA中的每一个状态对应NFA中的一组状态。即由于NFA中的f是多值的，所以在读入一个输入符号后可能达到的状态是集合，而子集法就是用DFA的状态记录该状态的集合。第41页，共117页，2023年，2月20日，星期四确定化的有关运算（2）Move(I,a)——状态集合I的a弧转换假定I是状态集的一个子集，a是Σ中的一个字符，定义

Ia

＝ε_closure(J)其中J是所有那些可从I中的某一状态出发经过一条a弧而到达的状态结的全体。

(3)Ia＝ε_closure(Move(I,a))（1）ε_closure(I)——状态集合I的ε闭包(等价状态集)

设I是状态集的一个子集，ε_closure(I)定义为：

a.若S∈I，则S∈ε_closure(I)；

b.若S∈I，那么从S出发经过任意ε弧而能到达的任意状态S’都属于ε_closure(I)；第42页，共117页，2023年，2月20日，星期四题：有一个状态图如下：1526aεε4a7εε3a8ε假定I=ε_closure(1)＝{1,2}从状态集I出发经过一条a弧而能到达的状态结全体J为{5,3,4}；而ε_closure(J)={5,6,2,3,8,4,7}例第43页，共117页，2023年，2月20日，星期四NFA的确定化从NFAN＝(K,Σ,f,K0,Kt)构造一个DFAM＝(S,Σ,D,S0,St)，其中

(1)S是由K一些子集组成；

(2)M与N的输入字母表相同，都是Σ；

(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,…,

Se]∩Kt≠Φ

}第44页，共117页，2023年，2月20日，星期四子集化的具体过程为了方便起见，令Σ中只有a,b两个字母，即Σ＝{a,b}（1）构造一张表，此表的每一行有三列，第一列为I，第二列为Ia，第二列为Ib。即IIaIbε_closure(K0)首先置该表的第一列为ε_closure(K0)。（2）一般而言，若某一行的第一列的状态子集已确定，例如记为I，则可以求出Ia和Ib

；第45页，共117页，2023年，2月20日，星期四子集化的具体过程（续）（3）检查Ia和Ib是否已在表的第一列中出现，把未曾出现者填入到后面空行的第一列位置上。（4）对未重复Ia

、Ib的新行重复上述过程(2)、(3)，直到所有第二列和第三列的子集全部在第一列中出现；上述过程必定在有限步内终止，因为N的状态子集的个数是有限的。我们也可将表看成状态转换矩阵，即把其中每个子集看成一个状态，就可以由这张表唯一刻划出一个确定的有穷自动机DFA。其初态就是该表的第一行第一列的ε_closure(K0)，终态就是那些含有的Kt子集。第46页，共117页，2023年，2月20日，星期四例题：将下图NFAN确定化。12εεbεε3a7ε0ε45b6εε8a910bIIaIbSab{0,1,2,4,7}{1,2,3,4,6,7,8}{1,2,4,5,6,7}012{1,2,3,4,6,7,8}{1,2,3,4,6,7,8}{1,2,4,5,6,7,9}113{1,2,4,5,6,7}{1,2,3,4,6,7,8}{1,2,4,5,6,7}212{1,2,4,5,6,7,9}{1,2,3,4,6,7,8}{1,2,4,5,6,7,10}314{1,2,4,5,6,7,10}{1,2,3,4,6,7,8}{1,2,4,5,6,7}412解：(1)构造转换矩阵第47页，共117页，2023年，2月20日，星期四接上页(2)对表中所有的子集重新命名，其中0是初态，4是终态。∴对应的DFAM：0124ba3aabbabab第48页，共117页，2023年，2月20日，星期四例题：将下图确定化：解：(1)构造转换矩阵II0I1S01{s,x,y}{w}{s,x,y}ABA{w}{}{y,s,x,z}BC{s,x,y,z}{w,s,x,y}{s,x,y}CDA{w,s,x,y}{w}{s,x,y,z}DBCsyxwz1ε0ε101ε第49页，共117页，2023年，2月20日，星期四接上页∴DFAM为：ABDC0110101第50页，共117页，2023年，2月20日，星期四3.3.6消除不可达状态

有穷自动机的多余状态：是指这样的状态，从该自动机的开始状态出发，任何输入串也不能达到的那个状态。

01S0S1S5S1S2S7S2S2S5S3S5S7S4S5S6S5S3S1S6S8S0S7S0S1S8S3S6第51页，共117页，2023年，2月20日，星期四3.3.7DFA的化简对已求得的DFA，可以进一步将其化简，即求最小DFA。也就是对于任意给定的DFAM构造另一个DFAM’，使L(M)=L(M’)，且DFAM’的状态个数少于DFAM的状态个数。消除多余状态

DFAM状态最少化的过程：把M的状态集分割成一些不相交的子集，使得任何不同的两个子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的。第52页，共117页，2023年，2月20日，星期四有关分割法所用的概念定义3.8等价

设s,t是M的两个不同的状态，s,t等价的意思是：如果从状态s出发能读出某个字α而停于终态，那么同样从t出发也能读出同一个字α而停于终态；反之，若能从t出发读出某个字α而停于终态，那么同样从s出发也能读出字α而停于终态。等价的条件：(1)一致性条件——状态t,s必须同时是可接受状态或不可接受状态；(2)蔓延性条件——对于所有输入符号，状态s和状态t必须转换到等价的状态里(注：状态s对应有输入a而状态t无输入a时，这两个状态是不等价的）。第53页，共117页，2023年，2月20日，星期四有关分割法所用的概念定义3.9可区分若DFAM中的两个状态s,t不等价，则这两个状态是可区别的。例如：终态和非终态是可区别的（读出ε）；下图中的状态2与状态3（读出b字）；

0124ba3aabbabab第54页，共117页，2023年，2月20日，星期四分割法(1)把K的终态和非终态分开，分成两个子集——终态组和非终态组，形成基本分划П；显然，属于这两个不同子集的状态是可区别的。(2)假定到某个时候П含有m个子集，记П={I(1),I(2),……,I(m)}，若存在一个输入字符a使得Ia(i)不全包含在现行П的某个子集I(j)中，就将I(j)一分为二；至此把I(i)分成两半，形成新的划分П

new。第55页，共117页，2023年，2月20日，星期四分割法（续）

(3)重复上述过程(2)，直到П所含的子集不再增长为止，此时得到最后的划分П

finish；此时，П中的所有子集已是不可再分的了。也就是说，同个子集中的状态都是互相等价的，而不同子集中的状态则是可区别的。

(4)对于П

finish中的每一个子集，选取子集中的一个状态代表其它状态，这个代表就是化简了的DFAM’的状态。例如：假定I={S1,S2,S3}这样一个子集，则可选S1代表这个子集，那么在原自动机中，凡导入到S2,S3的弧都导入到S1,然后把S2,S3结点从原来的状态集合中删除，因为它们已成了一些多余的状态（从开始状态出发，任何输入串也不能达到的状态）。第56页，共117页，2023年，2月20日，星期四对划分的说明例如：假定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或读不出字α或虽可读出字α但不到达终态，或情况恰好相反。因而字α将S1和S2区别开来，也就是说，I(i1)和I(i2)中的状态是可区别第57页，共117页，2023年，2月20日，星期四若I中含有原来的初态，则S1是新初态；若含有原来的终态，则S1是新终态。经过消除多余状态和合并等价状态而得到的DFAM’，便是最简化的（包含最少状态的）DFA。化简后初态和终态的确定第58页，共117页，2023年，2月20日，星期四a134267=>5aaaaaabbbbbbb例：化简下图中的DFA解：(1)把M的状态分成两组：{1,2,3,4}、{5,6,7}；第59页，共117页，2023年，2月20日，星期四例：DFA化简

(2)考察{5,6,7}，由于{5,6,7}a={4,7}，因此对{5,6,7}一分为二：{5}、{6,7}；

(3)考察{1,2,3,4}，由于{1,2,3,4}a={1,4,6,7}，因此对{1,2,3,4}一分为二：{1,2}、{3,4}；

(4)考察{3,4}，由于{3,4}a={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}∴化简了的DFAM’为：第60页，共117页，2023年，2月20日，星期四例：化简后的DFA化简后的DFAaa1346=>5aabbbbba第61页，共117页，2023年，2月20日，星期四例思考题：将下列DFAM最小化。0124ba3aabbabab解：整个划分为：{0,2}、{1}、{3}、{4}104a3abbabab{0,1,2,3}{4}b:{0,2},{1},{3},{4}第62页，共117页，2023年，2月20日，星期四例将下图DFA最小化。解：(1)把M的状态分成两组：终结组{C}、非终结组{A,B,D}；

(2)考虑{A,B,D}，由于{A,B,D}1={A,C}，因此对{A,B,D}一分为二，分成{A}、{B,D}ABDC0110101ABC011010第63页，共117页，2023年，2月20日，星期四例(续)至此，整个集合含有三组：{A}、{B,D}、{C}。最后，令状态B代表{B,D}，将原来导入到D的弧都导入到B，并删除D。这样，所得的化简DFAM’为：ABC011010原因：{B,D}0时B无出边，D有出边，不满足蔓延性条件正确的划分：{A}、{B}、{C}、{D}第64页，共117页，2023年，2月20日，星期四例化简如下DFAM1401101002037500161100解：整个划分为：{0,1}、{2,5}、{3}、{4,7}、{6}，用0,1,2,3,4分布代替子集{0,1}、{2,5}、{3}、{4,7}、{6}0012100431100第65页，共117页，2023年，2月20日，星期四

3.4正规文法和有穷自动机间的转换3.4.1(1)正规文法G→NFAM：构造规则：

(a)Σ与G中的VT相同；

(b)M中的K与G中的VN相同，即文法G中的每个非终结符生成自动机M中的一个状态，G的开始符号S是M的初态；增加一个新的状态Z，作为接受状态。

(c)对产生式A→tB，其中t∈VT或ε，A,B∈VN，构造M的一个转换函数f(A,t)=B；

(d)对产生式A→t，构造M的转换函数f(A,t)=Z（终态集）。第66页，共117页，2023年，2月20日，星期四正规文法G→NFAM

例1课本P73构造正规文法G[S]等价的NFAM。

G[S]:S→+NS→-NS→dNS→dN→dNN→d解：与文法G等价的NFAM如下图：q0q1q2+d-dd第67页，共117页，2023年，2月20日，星期四正规文法G→NFAM

例2构造正规文法G[S]等价的NFAM。

G[S]:S→aAS→bBS→bA→aBA→bAB→aSB→bAB→ε解：与文法G等价的NFAM如下图：SaZABbbababε第68页，共117页，2023年，2月20日，星期四3.4.1左线性文法->NFAM转换规则：

(a)文法的开始符号S是M的终态。

(b)引入一个新的非终结符R作为初态结点。

(c)对于文法中的每一个形如A->a的产生式，从初态结点画一条弧到结点A，且用a标记该弧线。

(d)对于文法中的每一个形如A->Ba的产生式，从结点B画一条弧到结点A，且用a标记该弧线。第69页，共117页，2023年，2月20日，星期四3.4.1左线性文法->NFAM例：G[S]:S->S1S->A1A->A0A->0

RAS0011第70页，共117页，2023年，2月20日，星期四3.4.2NFAM→正规文法G转换规则：

(a)对转换函数f(A,t)=B，写成产生式A→tB；

(b)对终态Z，增加产生式Z→ε；

(c)VN为NFA所有状态中的标记（K），VT为NFA的Σ，NFA的初态就是开始符号S。第71页，共117页，2023年，2月20日，星期四例例：给出与NFA等价的正规文法GAaDBbbaabCb解：与NFA等价正规文法G=(VN,VT,P,S)=({A,B,C,D},{a,b},P,A)，其中P为：

A→aBA→bDB→bCC→aAC→bDC→εD→aBD→bDD→ε第72页，共117页，2023年，2月20日，星期四3.5正规表达式与FA单词的描述工具：正规文法正规文法（3型文法）的形式定义设G=(VN,VT,P,S)为一文法，若G的任何产生式A→α或A→αB，其中A、B∈VN

，α∈VT*

。第73页，共117页，2023年，2月20日，星期四正规文法的例子例：“无符号实数”定义<无符号实数>→d<余留无符号数>|.<十进小数>|e<指数部分><余留无符号数>→d<余留无符号数>|.<十进小数>|e<指数部分>|ε<十进小数>→d<余留十进小数><余留十进小数>→e<指数部分>|d<余留十进小数>|ε<指数部分>→d<余留整指数>|s<整指数><整指数>→d<余留整指数><余留整指数>→d<余留整指数>|ε其中s—正负符号+、－第74页，共117页，2023年，2月20日，星期四3.5.1单词的描述工具——正规式的定义正规式也叫正则表达式，用于描述称为正规集的语言。定义3.10字母表Σ上的正规式和正规集的递归定义为：(1)ε和Φ是Σ上的正规式，它们所代表的正规集为{ε}{}(Φ)；(2)任何a∈Σ，a是Σ上的一个正规式，它所表示的正规集为{a}；(3)假定e1与e2都是Σ上的正规式，它们所表示的正规集为L(e1)和L(e2)，那么(e1)、e1|e2、e1•e2和e1*也是正规式，它们所表示的正规集分别为L(e1)、L(e1)∪L(e2)、L(e1)L(e2)、(L(e1))*(4)仅用有限次使用上述三步骤而定义的表达式方是Σ上的正规式，仅有这些正规式所表示的字集才是Σ上的正规集。第75页，共117页，2023年，2月20日，星期四正规式运算符优先关系①‘|’(或)<‘•’(连接)<‘*’(闭包)②‘*’、‘|’都满足左结合注：连接号可省略第76页，共117页，2023年，2月20日，星期四例１：正规式正规式a|baba*ba*(a|b)(a|b)a(a|b)*(a|b)*(aa|bb)(a|b)*正规集{a,b}{ab}{ε,a,aa,…任意个a的串}Σ上所有以b为首后跟任意个a的字{aa，ab，ba，bb}Σ上所有以a为首的字Σ上所有含有两个相继的a或b的字第77页，共117页，2023年，2月20日，星期四例2

令Σ={l,d,.,e,+,-}，则Σ上的正规式d*(.dd*|ε)(e(+|-|ε)dd*|ε)l(l|d)*dd*正规集所有无符号的数标识符所有无符号整数第78页，共117页，2023年，2月20日，星期四定义3.11正规式等价

若两个正规式e1,e2所表示的正规集相等(即L(e1)=L(e2))，则e1,e2等价，记为e1=e2。例如：a|b=b|a，b(ab)*=(ba)*b，(a|b)*=(a*b*)*第79页，共117页，2023年，2月20日，星期四正规式的代数规律定理3.1设r,s,t为正规式（1）r|s=s|r“或”满足交换律（2）r|(s|t)=(r|s)|t“或”满足结合律（3）r(st)=(rs)t“连接”的可结合律（4）r(s|t)=rs|rt，(s|t)r=sr|tr分配律（5）εr=r=rεε的恒等式……参考课本P75定理3.1第80页，共117页，2023年，2月20日，星期四3.5.3正规式和有穷自动机的等价性正规式和有穷自动机的等价性由以下两点说明：(1)Σ上的非确定自动机M所能识别的字的全体L(M)是Σ上的一个正规集；（或对于Σ

上的NFAM，可以构造一个Σ

上的正规式R，使得L(R)=L(M)）(2)对于Σ上的每个正规集V，存在一个Σ上的确定有穷自动机M，使得V=L(M)；（或对于Σ

上的每个正规式R，可以构造一个NFAM，使得L(M)=L(R)）第81页，共117页，2023年，2月20日，星期四3.5.5NFAM→正规式R把状态图的概念拓广，令每条弧可用一个正规式作标记1.添加x,y结点构造NFAM’，其中x与所有的初始结ε弧连接，y与所有终态结ε弧连接。2.反复使用以下规则，消去M’中的所有结，直到只剩下x,y结；在消结过程中逐步用正规式来标记箭弧，其消结的规则如下：1R123R21R1R23第82页，共117页，2023年，2月20日，星期四NFAM→正规式R（续）1R12R21R1|R221R123R21R1R2*R33R3最后，x和y结点间弧上的标记则为所求的正规式R。第83页，共117页，2023年，2月20日，星期四例１NFAM的状态图如下，求正规式R，使得L(R)=L(M)。01a,b342ababa,ba,b1εyεε所求的正规式R=(a|b)*(aa|bb)(a|b)*1ε0a,

b(aa|bb)(a|b)*Y第84页，共117页，2023年，2月20日，星期四y例２NFAM的状态图如下，求正规式R，使得L(R)=L(M)。01aa,bbab,baab,baaa,bb解：正规式R=((aa|bb)|(ab|ba)(aa|bb)*(ab|ba))*0aa,bbxε(ab|ba)(aa|bb)*(ab|ba)ε第85页，共117页，2023年，2月20日，星期四例３有些自动机比较复杂，我们也并不完全按照上述规则进行转换。例如svutabababa,b可分四种走向（要点，划分图成多个子图,本题4个）：(1)s→u→t：a(ba)*a(a|b)*(2)s→u→v→t：ab(ab)*b(a|b)*(3)s→v→u→t：ba(ba)*a(a|b)*(4)s→v→t：b(ab)*b(a|b)*(((ε|b)a(ba)*)|((ε|a)b(ab)*))(a|b)+第86页，共117页，2023年，2月20日，星期四3.5.4正规式→NFA从正规式R构造NFA的算法：首先把正规式R表示成如下图的拓广转换图：xRy然后通过对R进行分裂和加进新结的方法，逐步把这个图转换变成每条弧标记为Σ的一个字符或ε。其转换规则如下：注：在整个分裂的过程中，所有新结均采用不同的名字，结点x,y为构造成的NFA的唯一的初态和终态。第87页，共117页，2023年，2月20日，星期四正规式转换系统Φxyεxεya(a∈Σ)xay

s|t(s,t是正规式)xsytstxsy1ts*xεy1εs正规式→NFA（续）第88页，共117页，2023年，2月20日，星期四正规式→NFA（续）例1R=(a|b)*abb构造NFAN，使得L(N)=L(R)。解：x(a|b)*abbyx(a|b)*y2abbxεy1abb2εabxεy1a2εab3b4b第89页，共117页，2023年，2月20日，星期四正规式→NFA（续）例2构造与正规式R=(a*b)*ba(a|b)*等价的最简DFAM，使得L(M)=L(R)。第90页，共117页，2023年，2月20日，星期四语法制导法用正规式的语法结构指导构造过程。首先构造识别ε和Σ中的任何符号的自动机，然后构造识别含一个选择（或）、并置（连接）和闭包算符的正规式的自动机。例如正规式R，首先把R分解成子表达式，然后使用以下构造规则为R构造NFA，对R的各种语法结构的构造规则具体描述如下：1.(a)对于正规式Φ

，所构造的NFA为：xy(b)对于正规式ε

，所构造的NFA为：xεy第91页，共117页，2023年，2月20日，星期四(c)对于正规式a(a∈Σ)

，所构造的NFA为：xay语法制导法（续）2.若s,t为Σ上的正规式，相应的NFA分别为N(s)和N(t)，则

(a)对于正规式R=s|t，所构造的NFA(R)如下：xyN(s)N(t)εεεε其中x,y分别是NFA(R)的初态和终态，从x到N(s)和N(t)的初态各有一条ε弧，从N(s)和N(t)的终态各有一条ε弧到y。第92页，共117页，2023年，2月20日，星期四语法制导法（续）

(b)对于正规式R=st，所构造的NFA(R)如下：N(t)xyN(s)其中N(s)的初态成了N(R)的初态,N(t)的终态成了N(R)的终态，N(s)的终态和N(t)的初态合并为N(R)的一个既不是初态也不是终态的状态。

(c)对于正规式R=s*，所构造的NFA(R)如下：其中，x和y分别是NFA(R)的初态和终态xyN(s)εεεε第93页，共117页，2023年，2月20日，星期四语法制导法（续）(d)对于正规式(s)，其NFA同s的NFA一样。每次构造新的状态时，都给它不同的名字，这样所有的状态都有不同的名字。根据上述方法构造的NFA具有以下性质：

(1)NFA(R)的状态数最多是R中符号和算符数的两倍（∵构造的每步最多引入两个新结点）；

(2)NFA(R)只有一个初态和一个终态；

(3)NFA(R)的每个状态（除终态）有一个用Σ的符号标记的向外的转换，或者最多两个向外的ε弧转换。例：为R=(a|b)*abb构造NFAN，使得L(N)=L(R)。解：参见书本P61第94页，共117页，2023年，2月20日，星期四综合题构造正规式R=(a|b)*(aa|bb)(a|b)*相应的DFA。解：(1)构造NFANx(a|b)*(aa|bb)(a|b)*yx(a|b)*y1aa|bb2(a|b)*aaaaxεy120εbbbε5εbaaxεy130εabbε5εab24b第95页，共117页，2023年，2月20日，星期四

4.4正规式和有穷自动机的等价性(2)对NFAN确定化：构造状态转换矩阵IIaIbSab{x,0,1}{0,1,3}{0,1,4}012{0,1,3}{0,1,3,2,5,y}{0,1,4}132{0,1,4}{0,1,3}{0,1,4,2,6,y}214{0,1,2,3,5,y}{0,1,3,2,5,y}{0,1,4,5,y}335{0,1,2,4,5,y}{0,1,3,5,y}{0,1,4,2,5,y}464{0,1,4,5,y}{0,1,3,5,y}{0,1,4,2,5,y}564{0,1,3,5,y}{0,1,3,2,5,y}{0,1,4,5,y}635第96页，共117页，2023年，2月20日，星期四

4.4正规式和有穷自动机的等价性∴DFAM为：0a312baba4ba5b6baabab(3)对DFAM进行化简0a312bababa,b整个划分为：{0},{1},{2},{3,4,5,6}第97页，共117页，2023年，2月20日，星期四§3.5.6正规文法和正规式间的转换一个正规语言，可以由正规文法来定义，也可以由正规式定义。任意正规文法，存在一个对应的正规式；反之亦然。方法：1.直接转换2.间接转换正规文法→有穷自动机→正规式正规式→有穷自动机→正规文法第98页，共117页，2023年，2月20日，星期四§3.5.6正规式->正规文法将Σ上的一个正规式r，转换为正规文法G=(VN,VT,P,S).1.令VT=

Σ2.S->r,S为开始符号3.若x和y都是正规式，则 产生式 重写为：r1. A->xy A->xBB->yr2. A->x*y A->xAA->yr3. A->x|y A->xA->y不断做变换，直到每个产生式右端最多只含一个VN

第99页，共117页，2023年，2月20日，星期四§3.5.6正规式->正规文法例 将正规式R=a(ad) 转换为相应的正规文法。

VT={a,d} Sa(ad)r1.SaA A(ad)r2.A(ad)A A

r3. SaA AaA AdA

A

VN={S,A}第100页，共117页，2023年，2月20日，星期四§3.5.6正规文法->正规式对G=(VN,VT,P,S),存在一个Σ=VT上的正规式R，使得L(R)=L(G)。在此介绍2种转换方法：一：1.令Σ=VT2.转换规则 文法产生式 正规式 AxBBy A=xy AxAyA=xy Axy A=xy不断做变换，直到只剩下一个开始符号定义的产生式，且该产生式右端不含VN

第101页，共117页，2023年，2月20日，星期四§3.5.6正规文法->正规式例子例文法G[s]:SaA AaA AdA Sa Aa Ad解答：SaAa AaAadAd A(ad)A(ad) A(ad)(ad)⑤

S=a(ad)(ad)a =a((ad)(ad)) =a((ad))所以，R=a(ad)第102页，共117页，2023年，2月20日，星期四§3.5.6正规文法->正规式对G=(VN,VT,P,S),存在一个Σ=VT上的正规式R，使得L(R)=L(G)。在此介绍2种转换方法：二：方程组求解法课本P83如果S=aS+b则有S=a*b例子：关于标识符的文法

<标识符>-><标识符>字母

<标识符>-><标识符>数字

<标识符>->字母<标识符>=<标识符>字母+<标识符>数字+字母<标识符>=<标识符>（字母+数字）+字母所以，<标识符>=字母(字母+数字)*即，标识符可以用正规式:字母(字母|数字)*来表示第103页，共117页，2023年，2月20日，星期四补充：右线性语言的封闭性3型文法中的右线性文法所对应的语言，右线性语言。右线性语言恰好是正则集。对右线性语言L1,L2进行并、积和闭包运算的结果，仍然是右线性语言。设L，L1,L2是右线性语言，则有:(1)L1∪L2为右线性语言(2)L1L2为右线性语言(