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

1、第三章 有穷自动机,要点： 1. DFA和NFA的定义 2. NFADFA的转换； 3. DFA的化简 4. 正规文法、正规式、有穷自动机之间的相互转换；,编译原理,有穷自动机,有穷自动机（或有限自动机）作为一种识别工具，它能正确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合。引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。 分类：确定的有穷自动机（DFA） 不确定的有穷自动机（NFA）,3.1 概述 有穷自动机（FA）,有穷自动机（FA，Finite Automata）是一种有限离散数字系统的抽象数学模型。 这个系统具有有限数目的内部“状态”。 所谓状

2、态，是可以将事物区分开的一种标识。例如：数字电路（0，1），十字路口的红绿灯等都是离散状态系统，其状态数目是有限的。连续状态系统则如水库的水位、室内温度变化等。 电梯的控制机制，不需要保存所有以前的服务要求，仅需记住当前的层次、运动的方向以及未满足的服务要求。 文本编辑程序和词法分析程序是有限状态系统，计算机本身和人的大脑也可看成有限状态系统。,有穷自动机（FA）,数字系统：可以从一个状态移动到另一个状态；每次状态转换，都上由当前状态及一组输入符号确定的；可以输出某些离散的值集。 FA：一个状态集合；状态间的转换规则；通过读头来扫描的一个输入符号串。 读头：从左到右扫描符号串。移动（扫描）是由

3、状态转换规则来决定的。,d,d,d,;,.,d,d,+,;,输入符号串,一个FA的例子,读头,数字,接收：若扫描完输入串，且在一个终止状态上结束。 阻塞：若扫描结束但未停止在终止状态上；或者不能扫描完输入串（如遇不合法符号）。 不完全描述：某些状态对于某些输入符号不存在转换。,练习：+34.567 .123 3.4.5,=,8,0,;,0,1,3,4,2,5,6,e,n,i,L,字母,字母,字母,字母,数字,数字,数字,=,=,；,；,0,1,2,4,5,6,3,L,i,n,e,=,8,0,;, id , Line, = , , num, 80, ;, ,数字,数字,字母,字母,1,1,=,=

4、,0,0,0,3,;,;,1,输入符号串,输出,有限控制器,读头,other,3.2 有穷自动机的形式定义,DFA: Deterministic Finite Automata NFA: Nondeterministic Finite Automata DFA的定义 定义3.1 一个确定的有穷自动机(DFA) M是一个五元组： M = ( Q, , t, q0, F ) (1)Q是一个非空有穷集合，它的每一个元素称为一个状态； (2)是一个有穷字母表，它的每一个元素称为一个输入字符； 也称为输入符号字母表,确定的有穷自动机DFA的定义（续）,(3) t是从Q到Q的一个单值映射； t(q,a)=

5、q， 其中q, qQ 说明：当前状态为q ，输入字符a时，将转换到下一个状态q ，把q称为q的一个后继状态。 DFA的确定性就表现在t是单值函数，即对任意状态qQ，输入符号a，t(q,a)唯一确定一个状态。 (4)q0Q，是唯一的初态； (5)F是Q的子集，是一个终态集，终态也称为可接收状态或结束状态。,确定的有穷自动机DFA的表示,3.2.1 状态转换图 设DFA有m个状态，n个输入字符，那么这个图含有m个状态结点，每个结点最多有n条箭弧射出和别的结点相连接，每条弧用中的一个不同输入符号作记号。整个图含有唯一的一个初态和若干个（可以0个）终态结。 习惯上，初态结可以用“=”或“”表示，终态结

6、用双圆圈表示或标以“+”。对t(q,a)=q指从状态结q到状态结q画标记a的弧。,例,题：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的状态图：,确定的有穷自动机DFA的表示（续）,3.2.2 状态转换矩阵 矩阵的行表示状态，列表示输入字符，矩阵元素表示相应的状态行在输入字符列下的新的状态，即t(k,a)的值。,例（题同）,解：该DFA M的矩阵表示,t(0,a)=1， t(0,b)=2，

7、t(1,a)=3， t(1,b)=2， t(2,a)=1， t(2,b)=3， t(3,a)=3， t(3,b)=3,3.2.3 有关自动机术语,(1)道路：对于*中的任何符号串，若存在一条从初态到某终态的路径。 (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 *,例,解：t(0, abb

8、a) = 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所识别（所接受）。,3.2.4 有关确定有穷自动机的结论,把DFA M所能接受的所有符号串（符号串的全体）记为L(M)。 上的一个字集V*是正规的，当且仅当存在一个上的确定有穷自动机M，使得L(M)=V。,有限自动机识别的语言 例子,例：下图中的自动机所能识别的语言是什么？,q0,q2,q1,q3,a,b,b,a,b,a,定义3.4 一个不确定的有穷自动机NFA N也是一个五元组：

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

10、同的字且可以是空字）作标记（或称输入字）。整个图中至少含有一个初态节以及若干个（可以是0个）终态节。 某些节既可以是初态节也可以是终态节。,例,题：一个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,解：其状态图如下：,例,如下状态图也是一个NFA,有关非确定有穷自动机的术语,对于*中的任何一个串t可被NFA M识别是指：若对这个字（串）t存在一条从某个初态节到某一个终态节的道路，且这条道路上所有弧的标记字依序连接起来的字符串（不理睬那些标记为的弧）等于t，则t可识别（

11、或可接受） 若M的某些节点既是初态节也是终态节，或存在一条从某个初态节到某个终态节的道路，则空字可为M所识别（所接受）。,NFA和DFA的关系,DFA是NFA的一个特例。 对于每个NFA M，存在一个DFA M，使得L(M)=L(M) 对于任何两个有穷自动机M和M，如L(M)=L(M)则称M和M是等价的。 如果M仅通过重新标记它的状态，就能转换成M，则M和M称为同构的。 对于每一个NFA M，存在一个等价的、具有最少状态个数的DFA M，对于其它的DFA M”，若M”的状态个数与M相同且等价于M，则必然有M”与M同构，即：M在结构上是唯一的。,3.3 NFA DFA的转换（NFA的确定化）,通

12、过以下步骤，可以将一个NFA转换为等价的DFA： 1.寻找并消除空移环路； 2.消除余下的空移； 3.确定化 子集法、造表法； 4.DFA的最小化构造状态集合的划分,3.3.1 NFA中空移环路的寻找和消除,空移环路： 一个空移环路，是一个从状态A开始，并以状态A结束的空移动序列。,消除方法： 合并环路上的节点为新节点。 若含初态，则新节点为初态。 若含终态，则新节点为终态。 课本P53 例3.4,3.3.2 NFA的消除空移,A,B,a1,q1,q2,qn,a2,an,a1,an,a2,消除方法： 删除弧，产生新弧。 若A为初态，则B结点也为初态。 若B为终态，则A结点也为终态。,3.3.3

13、 利用状态转换表消除空移,首先找出直接经由一个空移到达某个终态的所有状态。每找到这样一个状态，标记为终态。 然后，考虑消除与未被标记为终态的那些状态相关的空移。 对表中每一个具有射出连线的状态继续按上述方式处理，直到状态表不再变动为止。 从表中删除列和没有任何元素的空行，便得到一个不含空移的状态转换表。,表3.2 图3.4中NDFA标记状态后的情况,表3.3 删除空移后的状态转换图,3.3.4 NFA的确定化子集法,一个例子( 无空移) p55 图3.9 介绍一种称子集法的算法来将NFA转换成接收同样语言的DFA。 算法的基本思想是：把DFA中的每一个状态对应NFA中的一组状态。即由于NFA中

14、的t是多值的，所以在读入一个输入符号后可能达到的状态是集合，而子集法就是用DFA的状态记录该状态的集合。,将NDFA M=(Q, ,t,Q0,F) 转换为DFA M=(Q, ,t,q0,F)的步骤：,M的状态集Q是由M的状态集Q的所有子集组成的。用p1,p2, ,pi表示Q的元素。 若p是M的一个终态，则M中的每一个包含p的状态,p,都是M的一个终态。 若S=S1,S2,Sj是M的初态，则S=S1,S2,Sj是M的初态。 令p1,p2,pn是M中的一个状态，其中p1,p2,pn是M中的状态。对某个输入符号a，考虑M中的转换函数：t(p1,a), t(p2,a), , t(pn,a)，按以下方法

15、得到M的转换函数t: a. 令t(p1,a)U t(p2,a)UU t(pn,a)=q1,q2,qr b. 置t(p1,p2,pn,a)=q1,q2,qr 对M每一状态和每个输入符号a，重复步骤4.,利用状态表将NDFA转换为DFA。以表3.3为例,3.3.5 确定化-造表法,（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是

16、状态集的一个子集， _closure(I)定义为： a. 若SI，则S _closure(I)； b. 若SI，那么从S出发经过任意弧而能到达的任意状态S都属于_closure(I)；,1. 有关定义,题：有一个状态图如下：,假定 I= _closure(1)1, 2 从状态集I出发经过一条a弧而能到达的状态结全体J为5, 3, 4； 而_closure(J) =5, 6, 2, 3, 8, 4, 7,例,NFA的确定化,从NFA N (Q, , t, q0, F)构造一个DFA M (Q, , t, q0, F)，其中 (1) Q是由Q一些子集组成； (2) M与N的输入字母表相同，都是；

17、(3)t定义： t(q1, q2, qj, a)=q1, q2, qi，其中 _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 ,具体过程,为了方便起见，令中只有a,b两个字母，即a, b （1）构造一张表，此表的每一行有三列，第一列为I，第二列为Ia，第二列为Ib。即,首先置该表的第一列为_closure(q0)。,（2）一般而言，若某一行的第一列的状态子集已确定，例如记为I，则可以求出Ia和Ib ；,具

18、体过程（续）,（3）检查Ia和Ib是否已在表的第一列中出现，把未曾出现者填入到后面空行的第一列位置上。 （4）对未重复Ia 、 Ib的新行重复上述过程(2)、(3) ，直到所有第二列和第三列的子集全部在第一列中出现；,上述过程必定在有限步内终止，因为N的状态子集的个数是有限的。我们也可将表看成状态转换矩阵，即把其中每个子集看成一个状态，就可以由这张表唯一刻划出一个确定的有穷自动机DFA。其初态就是该表的第一行第一列的_closure(q0) ，终态就是那些含有F的子集。,例,题：将下图NFA N确定化。,解：(1)构造转换矩阵,接上页,(2)对表中所有的子集重新命名，其中0是初态，4是终态。

19、对应的DFA M：,例,题：将下图确定化：,解：(1)构造转换矩阵,接上页, DFA M为：,例子3.7：求与右图等价的DFA= (Q,t,q0,F),=x,y Q=q0,q1,q2,q3,q0,q1,q0,q1,q2,q3 F=q3,q0,q3,q1,q3,q2,q3,q0,q1,q2,q3,. 确定化后的状态转换矩阵,3.3.6 消除不可达状态,有穷自动机的多余状态：是指这样的状态，从该自动机的开始状态出发，任何输入串也不能达到的那个状态。,3.3.7 DFA的化简,对已求得的DFA，可以进一步将其化简，即求最小DFA。也就是对于任意给定的DFA M构造另一个DFA M，使L(M)=L(M

20、)，且DFA M的状态个数少于DFA M的状态个数。 消除多余状态 DFA M状态最少化的过程： 把M的状态集分割成一些不相交的子集，使得任何不同的两个子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的。,有关分割法所用的概念,定义3.7 等价 设s,t是M的两个不同的状态，s,t等价的意思是：如果从状态s出发能读出某个字而停于终态，那么同样从t出发也能读出同一个字而停于终态；反之，若能从t出发读出某个字而停于终态，那么同样从s出发也能读出字而停于终态。,等价的条件： (1)一致性条件 状态t,s必须同时是可接受状态或不可接受状态； (2)蔓延性条件 对于所有输入符号，状态s和状态t

21、必须转换到等价的状态里(注：状态s对应有输入a而状态t无输入a时，这两个状态是不等价的）。,有关分割法所用的概念,定义3.8 可区分 若DFA M中的两个状态s,t不等价，则这两个状态是可区别的。 例如：终态和非终态是可区别的（读出）； 下图中的状态2与状态3（读出b字）；,分割法,(1)把Q的终态和非终态分开，分成两个子集 终态组和非终态组，形成基本分划；显然，属于这两个不同子集的状态是可区别的。 (2)假定到某个时候含有m个子集，记=I(1), I(2), , I(m)，若存在一个输入字符a使得Ia( i )不全包含在现行的某个子集I( j )中，就将I( j )一分为二；至此把I( i

22、)分成两半，形成新的划分 new。,分割法（续）,(3)重复上述过程(2)，直到所含的子集不再增长为止，此时得到最后的划分 finish； 此时， 中的所有子集已是不可再分的了。也就是说，同个子集中的状态都是互相等价的，而不同子集中的状态则是可区别的。 (4)对于 finish中的每一个子集，选取子集中的一个状态代表其它状态，这个代表就是化简了的DFA M的状态。 例如：假定I=S1, S2, S3这样一个子集，则可选S1代表这个子集，那么在原自动机中，凡导入到S2, S3的弧都导入到S1,然后把S2, S3结点从原来的状态集合中删除，因为它们已成了一些多余的状态（从开始状态出发，任何输入串也

23、不能达到的状态）。,对划分的说明,例如：假定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 )中的状态是可区别,若I中含有原来的初态，则S1是新初态；若含有原来的终态，则S1是新终态。 经

24、过消除多余状态和合并等价状态而得到的DFA M，便是最简化的（包含最少状态的）DFA。,化简后初态和终态的确定,例：化简下图中的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=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

25、,7 化简了的DFA M为：,例：化简后的DFA,化简后的DFA,例,思考题：将下列DFA M最小化。,解：整个划分为：0,2、1 、3、4,0,1,2,34 b:0,2,1,3,4,例,将下图DFA最小化。,解：(1)把M的状态分成两组：终结组C、非终结组A,B,D； (2)考虑A,B,D，由于A,B,D1=A,C，因此对A,B,D一分为二，分成A、B,D,例(续),至此，整个集合含有三组：A、B,D、C。 最后，令状态B代表B,D，将原来导入到D的弧都导入到B，并删除D。这样，所得的化简DFA M为：,原因：B,D0 时B无出边，D有出边，不满足蔓延性条件 正确的划分：A、B、C、D,例,

26、化简如下DFA M,解：整个划分为：0,1、2,5、3、4,7、6，用0,1,2,3,4分布代替子集0,1、2,5、3、4,7、6,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的转换函数t(U,a)=Z（终态集）。,正规文法GNFA M 例3.10 课本P6

27、9,构造正规文法GS等价的NFA M。 GS: S+N S-N Sd N Sd NdN Nd,解：与文法G等价的NFA M如下图：,d,正规文法GNFA M 例2,构造正规文法GS等价的NFA M。 GS: SaA SbB Sb AaB AbA BaS BbA B,解：与文法G等价的NFA M如下图：,3.4.1 左线性文法-NFA M,转换规则： (a) 文法的开始符号S是M的终态。 (b) 引入一个新的非终结符R作为初态结点。 (c) 对于文法中的每一个形如U-a的产生式，从初态结点画一条弧到结点U，且用a标记该弧线。 (d) 对于文法中的每一个形如U-Va的产生式，从结点V画一条弧到结点

28、U，且用a标记该弧线。,3.4.1 左线性文法-NFA M,例：GS: S-S1 S-A1 A-A0 A-0,3.4.2 NFA M 正规文法G,转换规则： (a) 对转换函数t(U,a)=V，写成产生式UaV； (b) 对终态Z，增加产生式Z； (c) VN为NFA所有状态中的标记（Q），VT为NFA的， NFA的初态就是开始符号S。,例,例：给出与NFA等价的正规文法G,解：与NFA等价正规文法G=(VN, VT, P, S)=(A,B,C,D,a,b, P, A)，其中P为： AaB AbD BbC CaA CbD C DaB DbD D ,3.5 正规表达式与FA,单词的描述工具：正规

29、文法 正规文法（3型文法）的形式定义 设G=( VN, VT, P, S)为一文法，若G的任何产生式A 或A B ，其中A、B VN ， VT* 。,正规文法的例子,例：“无符号实数”定义 d | . | e d | . | e | d e | d | d | s d d | 其中s 正负符号+、,3.5.1 单词的描述工具正规式的定义,正规式也叫正则表达式，用于描述称为正规集的语言。 定义3.9 字母表上的正规式和正规集的递归定义为： (1)和是上的正规式，它们所代表的正规集为 ()； (2)任何a，a是上的一个正规式，它所表示的正规集为a； (3)假定e1与e2都是上的正规式，它们所表示的

30、正规集为L(e1)和L(e2)，那么(e1)、 e1| e2、 e1 e2和e1*也是正规式，它们所表示的正规集分别为 L(e1)、L(e1)L(e2)、 L(e1) L(e2)、 (L(e1) * (4)仅用有限次使用上述三步骤而定义的表达式方是上的正规式，仅有这些正规式所表示的字集才是上的正规集。,正规式运算符优先关系,|(或) (连接) *(闭包) *、|都满足左结合 注：连接号可省略,例：正规式,例2,令=l, d, ., e, +, -，则上的 正规式 d*(.dd*|) (e(+|-|)dd*| ) l (l|d)* dd*,正规集 所有无符号的数 标识符 所有无符号整数,定义 3

31、.10 正规式等价,若两个正规式e1, e2所表示的正规集相等(即L(e1)=L(e2)，则e1, e2等价，记为e1=e2。 例如： a|b=b|a ， b(ab)*=(ba)*b， (a|b)*=(a*b*)*,正规式的代数规律,定理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 的恒等式 参考课本P71定理3.1,3.5.3 正规式和有穷自动机的等价性,正规式和有

32、穷自动机的等价性由以下两点说明： (1)上的非确定自动机M所能识别的字的全体L(M)是上的一个正规集； （或对于 上的NFA M，可以构造一个 上的正规式e，使得L(e)=L(M)） (2)对于上的每个正规集V，存在一个上的确定有穷自动机M，使得V=L(M)； （或对于 上的每个正规式e，可以构造一个NFA M，使得L(M)=L(e)）,3.5.4 正规式NFA,从正规式R构造NFA的算法： 首先把正规式R表示成如下图的拓广转换图：,R,然后通过对R进行分裂和加进新结的方法，逐步把这个图转换变成每条弧标记为的一个字符或。其转换规则如下：,注： 在整个分裂的过程中，所有新结均采用不同的名字，结点

33、x,y为构造成的NFA的唯一的初态和终态。,正规式 转换系统,a (a),s | t (s,t是正规式),st,s*,正规式NFA（续）,正规式NFA（续）例1,e=(a|b)*abb构造NFA N，使得L(N)=L(e)。,解：,正规式NFA（续）例,1. 构造与正规式e=(+|-|)dd*等价的最简DFA M，使得L(M)=L(e)。 2. 为e=(a|b)*abb构造NFA N，使得L(N)=L(e)。 3. 构造与正规式e=(a*b)ba(a|b)*等价的最简DFA M，使得L(M)=L(e)。,3.5.5 NFA M正规式e,把状态图的概念拓广，令每条弧可用一个正规式作标记 1.添加

34、x,y结点构造NFA M，其中x与所有的初始结弧连接，y与所有终态结弧连接。 2.反复使用以下规则，消去M中的所有结，直到只剩下x,y结； 在消结过程中逐步用正规式来标记箭弧，其消结的规则如下：,R1,R2,R1 R2,NFA M正规式R（续）,R1,R2,R1 | R2,R1,R2,R1 R2 *R3,R3,最后，x和y结点间弧上的标记则为所求的正规式R。,例,NFA M的状态图如下，求正规式e，使得L(e)=L(M)。,所求的正规式e=(a|b)*(aa|bb)(a|b)*,0,a, b,(aa|bb)(a|b)*,Y,y,例,NFA M的状态图如下，求正规式e，使得L(e)=L(M)。,

35、解：正规式R=(aa|bb) | (ab|ba)(aa|bb)*(ab|ba)*,0,aa,bb,x,(ab|ba)(aa|bb)*(ab|ba),例,有些自动机比较复杂，我们也并不完全按照上述规则进行转换。例如,可分四种走向（要点，划分图成多个子图,本题4个）： (1) sut： a(ba)*a(a|b)* (2) suvt： ab(ab)*b(a|b)* (3) svut： ba(ba)*a(a|b)* (4) svt： b(ab)*b(a|b)*,(|b)a(ba)*)|(|a)b(ab)*)(a|b)(a|b)*,综合题,构造正规式e=(a|b)*(aa|bb)(a|b)*相应的DFA

36、。,解：(1)构造NFA N,正规式和有穷自动机的等价性,(2)对NFA N确定化： 构造状态转换矩阵,正规式和有穷自动机的等价性, DFA M为：,(3)对DFA M进行化简,整个划分为：0,1,2,3,4,5,6,3.5.6 正规文法和正规式间的转换,一个正规语言，可以由正规文法来定义，也可以由正规式定义。任意正规文法，存在一个对应的正规式；反之亦然。 方法： 1.直接转换 2.间接转换 正规文法有穷自动机正规式 正规式有穷自动机正规文法,3.5.6 正规式-正规文法,将上的一个正规式r，转换为正规文法G=( VN, VT, P, S). 1.令VT= 2. S-r , S为开始符号 3.

37、 若x和y都是正规式，则 产生式 重写为： r1. A-xy A-xB B-y r2. A-x*yA-xA A-y r3. A-x|y A-x A-y 不断做变换，直到每个产生式右端最多只含一个VN,3.5.6 正规式-正规文法,例 将正规式R=a(ad)转换为相应的正规文法。 VT=a,d Sa(ad),r3. SaA AaA AdA A VN=S,A,r1. SaA A(ad),r2. A(ad)A A,3.5.6 正规文法-正规式,对G= ( VN, VT, P, S), 存在一个 = VT上的正规式e，使得 L(R)=L(e) 。在此介绍2种转换方法： 一： 1.令 =VT 2.转换规

38、则 文法产生式正规式 AxB ByA=xy AxAy A=xy Axy A=xy 不断做变换，直到只剩下一个开始符号定义的产生式，且该产生式右端不含VN,3.5.6 正规文法-正规式 例子,例 文法Gs:SaA AaA AdA Sa Aa Ad, S=a(ad)(ad)a =a(ad)(ad) =a(ad) 所以，t=a(ad),解答： SaAa, AaAadAd, A(ad)A(ad), A(ad)(ad),3.5.6 正规文法-正规式,二.方程组求解法 p78 例3.19 S-0A|1B|0|1 A-0S|1B|1 B-1S+0A 解：写出关于变量S、A、B的正规方程组： S=(0+1)+

39、0A+1B (1) A=1+0S+1B (2) B=1S+0A (3) 将(3)代入(1)和(2), 可得： S=(0+1)+0A+1(1s+0A)=(0+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)*

40、(0+10)(10*)1+0+1),3.6 DFA在计算机中的表示,要在计算机中表示一个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,3.6.2 表结构,在表结构中，每一个状态对应一个表，表中包括状态名，从该状态发出的弧数、每条弧上的标记（输入字母）以及弧达到状态所在表的首地址。 例3.22 p81,3.6.3 自动机的编程实现 p82,0: 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;