《第三章有穷自动机优秀课件.ppt》由会员分享，可在线阅读，更多相关《第三章有穷自动机优秀课件.ppt（74页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第三章有穷自动机第1页，本讲稿共74页3.1 有穷自动机的形式定义有穷自动机的形式定义 有穷状态自动机有穷状态自动机(Finite-stateAutomata或简称或简称FA)在识别功能上与正规在识别功能上与正规文法类等价，而且也等价于一个特殊类型文法类等价，而且也等价于一个特殊类型的语言产生器的语言产生器正规表达式正规表达式(RegularExpression)。因此许多简单的程序语言。因此许多简单的程序语言都可由都可由FA所识别。事实上，它是描述词法所识别。事实上，它是描述词法的有效工具，也是进行词法分析的主要理的有效工具，也是进行词法分析的主要理论基础。论基础。第2页，本讲稿共74页有穷
2、自动机分为两类：有穷自动机分为两类：（1）确定的有穷自动机）确定的有穷自动机(DeterministicFiniteAutomata简称简称DFA)（2）不确定的有穷自动机）不确定的有穷自动机(NondeterministicFiniteAutomata简称简称NFA)。第3页，本讲稿共74页3.1.1确定有穷自动机的形式定义确定有穷自动机的形式定义 一个一个DFAM(K，f，S，Z)，其中，其中()K是一个有限状态集合。是一个有限状态集合。()是一个字母表，它的每个元素称为一个输入字符。是一个字母表，它的每个元素称为一个输入字符。()S K，S称为初始状态称为初始状态,唯一。唯一。()Z K
3、，Z称为终态集合称为终态集合,终态也称可接受状态或结终态也称可接受状态或结束状态。束状态。()f是转换函数，是一个从是转换函数，是一个从K到到K的单值映射。的单值映射。f(ki，a)kj（ki,kj K,a）kj称为称为ki的一个后继状态。的一个后继状态。第4页，本讲稿共74页l确定性的体现：初始状态唯一；确定性的体现：初始状态唯一；转换函数转换函数为单值映射。为单值映射。例：例：设设DFAM=(S,U,V,Q，a,b，f，S，Q)其中其中f(S,a)U，f(S,b)Vf(U,a)Q，f(U,b)Vf(V,a)U，f(V,b)Qf(Q,a)Q，f(Q,b)Q因为（因为（1）初始状态唯一是）初始
4、状态唯一是S，（2）每个转换函数均为单值映射。）每个转换函数均为单值映射。所以该所以该FA为确定有穷自动机。为确定有穷自动机。第5页，本讲稿共74页3.1.2状态转换表状态转换表 nDFA的映射关系可以由一个矩阵表示，矩阵的映射关系可以由一个矩阵表示，矩阵的行标表示状态，列标表示输入字符，矩阵的行标表示状态，列标表示输入字符，矩阵元素表示元素表示f(s,a)的值，这个矩阵称为状态转的值，这个矩阵称为状态转换表。换表。f(S,a)Uf(S,b)Vf(U,a)Qf(U,b)Vf(V,a)Uf(V,b)Qf(Q,a)Qf(Q,b)QabSUVUQVVUQQQQ第6页，本讲稿共74页q1aaabbab
5、bq2q3q03.1.3状态转换图状态转换图图中标有图中标有的为开始状态，标有双圈的状态为终止状态。的为开始状态，标有双圈的状态为终止状态。若若f(Ki,a)=Kj，则从状态结点，则从状态结点Ki到状态到状态Kj画标记为画标记为a的弧。的弧。第7页，本讲稿共74页3.1.4自动机的等价性自动机的等价性为了讨论自动机的等价性，先对为了讨论自动机的等价性，先对DFA中的映射进行扩充。中的映射进行扩充。n扩充的转换函数扩充的转换函数fn设设Q K，函数，函数f(Q,)=Q，即如果输入字，即如果输入字符是空串，则仍停留在原来的状态上。符是空串，则仍停留在原来的状态上。n对对 Q K,T,t1*,f(Q
6、,Tt1)=f(f(Q,T),t1)该定义是一个递归定义，说明当自动机处该定义是一个递归定义，说明当自动机处在状态在状态Q且面临某个输入串且面临某个输入串Tt1时，则先应时，则先应用函数用函数f(Q,T)=P，然后应用函数，然后应用函数f(P,t1)。第8页，本讲稿共74页lDFA的确定性表现在转换函数的确定性表现在转换函数f：KK是一个单值函数，即对任何状态是一个单值函数，即对任何状态k K和输和输入符号入符号a，f(k,a)唯一地确定了下一个状唯一地确定了下一个状态，从状态转换图来看，若字母表态，从状态转换图来看，若字母表 含有含有n个输入字符，那么任何一个状态结点最多个输入字符，那么任何
7、一个状态结点最多有有n条弧射出，且每条弧以一个不同的输条弧射出，且每条弧以一个不同的输入字符标记。入字符标记。第9页，本讲稿共74页l自动机接受字符串自动机接受字符串x如果对于某一自动机如果对于某一自动机M=(K,f,S,Z)，x*，有，有f(S,x)=P，且，且P Z，则，则x为该自为该自动机动机M所接受（识别），即自动机从开始所接受（识别），即自动机从开始状态开始，在读完全部输入串以后，自动状态开始，在读完全部输入串以后，自动机恰恰到达终止状态，则该输入串能被该机恰恰到达终止状态，则该输入串能被该自动机所接受。自动机所接受。第10页，本讲稿共74页例：例：DFAM=(S,A,B,C,0,1
8、,S,S)，且且 定义为定义为(S,0)=B，(S,1)=A，(A,0)=C，(A,1)=S，(B,0)=S，(B,1)=C，(C,0)=A，(C,1)=B状态图表示，矩阵表示：状态图表示，矩阵表示：第11页，本讲稿共74页自动机处理字符串自动机处理字符串110101和和11101的轨迹的轨迹(S,110101)=(S,1),10101)=(A,10101)=(A,1),0101)=(S,0101)=(S,0),101)=(B,101)=(B,1),01)=(C,01)=(C,0),1)=(A,1)=S(接受接受)(S,11101)=(S,1),1101)=(A,1101)=(A,1),101
9、)=(S,101)=(S,1),01)=(A,01)=(A,0),1)=(C,1)=B(拒绝拒绝)第12页，本讲稿共74页l所有为自动机所有为自动机M所能接受的串组成一个集所能接受的串组成一个集合，称这个集合为自动机合，称这个集合为自动机M所能接受的语所能接受的语言，用言，用L(M)表示：表示：L(M)=t|f(S,t)Z，t*l对于任何两个有穷自动机对于任何两个有穷自动机M和和M，如果，如果L(M)=L(M)，则称，则称M与与M是等价的。是等价的。第13页，本讲稿共74页3.1.5非确定有穷自动机非确定有穷自动机nNFA定义定义一个不确定的有穷自动机一个不确定的有穷自动机NFAM是一个是一个
10、五元组：五元组：M=(K,f,S,Z)一个含有一个含有m个状态和个状态和n个输入字符的个输入字符的NFA可表示为一张状态转换图，该图含有可表示为一张状态转换图，该图含有m个个状态结，每个结可射出若干条状态结，每个结可射出若干条箭弧与别的箭弧与别的结点相连接，每条弧用结点相连接，每条弧用*中的一个字（不中的一个字（不一定要不同的字，且可以为空字）作标记一定要不同的字，且可以为空字）作标记（称输入字），整个图至少含有一个初态（称输入字），整个图至少含有一个初态结以及若干个终态结。结以及若干个终态结。第14页，本讲稿共74页lNFA与与DFA的区别的区别NFA有一个开始状态集，而有一个开始状态集，而
11、DFA只有一个只有一个开始状态。开始状态。NFA的映射是的映射是QQ的子集，是一个多的子集，是一个多值映射，而值映射，而DFA的映射是的映射是QQ，是一，是一个单值映射。个单值映射。DFA是是NFA的特例，对于每个的特例，对于每个NFAM，存，存在一个在一个DFAM，使得，使得L(M)=L(M)。第15页，本讲稿共74页l对于对于*中的任何一个串中的任何一个串t，如果存在一条从，如果存在一条从某一初态结到某一终态结的道路，且这条某一初态结到某一终态结的道路，且这条道路上的所有弧的标记依序连接成的串等道路上的所有弧的标记依序连接成的串等于于t，则称，则称t可为可为NFAM所识别（读出或接受）所识
12、别（读出或接受）。l若若M的某些结既是初态结，又是终态结，或的某些结既是初态结，又是终态结，或者存在一条从某个初态结到某个终态结的者存在一条从某个初态结到某个终态结的 道路，则空字可为道路，则空字可为M所接受。所接受。第16页，本讲稿共74页例：例：NFAM=(0,1,2,3,4,a,b,f,0,2,4)f(0,a)=0,3f(2,b)=2f(0,b)=0,1f(3,a)=4f(1,b)=2f(4,a)=4f(2,a)=2f(4,b)=4可用状态图或矩阵表示：可用状态图或矩阵表示：03412aabba,ba,ba,b第17页，本讲稿共74页3.2NFA到到DFA的转换的转换通过下述步骤可将一个
13、通过下述步骤可将一个NFA转换成等价转换成等价的的DFA：寻找并消除空移环路；寻找并消除空移环路；消除余下的空移；消除余下的空移；确定化。确定化。第18页，本讲稿共74页3.2.1空移环路的寻找和消除空移环路的寻找和消除第19页，本讲稿共74页3.2.2消除空移消除空移 n下面给出一个消除空移的算法。下面给出一个消除空移的算法。给定从状态给定从状态A到到B的一个空移的一个空移(即从状态即从状态A到到B经由经由 连线的一个转换，换言之，连线的一个转换，换言之，t(A,)=，B，)。置。置t(A,)=，对每个，对每个a和和Q，如果，如果Q t(B,a)，则将，则将Q加到加到t(A,a)。如果。如果
14、A是开始状态，则将是开始状态，则将B也加入开始状态集。也加入开始状态集。如果如果B是终止状态，则将是终止状态，则将A也加入终止状态也加入终止状态集。集。第20页，本讲稿共74页3.2.3利用状态转换表消除空移利用状态转换表消除空移 n利用利用FA的状态转换表，可以很容易地消除的状态转换表，可以很容易地消除空移。这种方法的基本步骤是：空移。这种方法的基本步骤是：n首先，找出直接经由一个空移到达某个终首先，找出直接经由一个空移到达某个终态的所有状态。每当找到这样一个状态，态的所有状态。每当找到这样一个状态，便将它标记为终态。便将它标记为终态。n然后，考虑消除与未被标记为终态的那些然后，考虑消除与未
15、被标记为终态的那些状态相关的空移。对表中每一个具有射出状态相关的空移。对表中每一个具有射出连线的状态继续按上述方式处理，直到状连线的状态继续按上述方式处理，直到状态转换表不再变动为止。态转换表不再变动为止。n最后从表中删除最后从表中删除列和没有任何元素的空行，列和没有任何元素的空行，便得到一个不含空移的状态转换表。便得到一个不含空移的状态转换表。第21页，本讲稿共74页3.2.4确定化确定化造表法造表法 n造表法是一种简单而有效的确定化方法。造表法是一种简单而有效的确定化方法。n定义：设定义：设NFAM=(Q,t,Q0,F)，假，假定定I是是M中状态集的一个子集，定义中状态集的一个子集，定义
16、_closure(I)如下：如下：n若若q I，则，则q_closure(I)；n若若q_closure(I)，q 是由是由q出发经多条出发经多条 弧到达的状态，则弧到达的状态，则q_closure(I)。第22页，本讲稿共74页l定义：假定定义：假定I是是NFAM中状态集的一个子集，中状态集的一个子集，a，定义，定义Ia=_closure(J)其中其中J是所有那些可从子集是所有那些可从子集I中的任一状态出中的任一状态出发，经过一条发，经过一条a连线连线(跳过跳过a连线前的连线前的连线连线)而到达的状态而到达的状态(结结)的全体。的全体。l造表法的具体步骤：造表法的具体步骤：假定给定的假定给定
17、的NFAM中中 仅含两个符号仅含两个符号a，b。可用如下方法将。可用如下方法将M确定化：采用造表的确定化：采用造表的方式，该表的每一行有三列方式，该表的每一行有三列(若若 中含有中含有n个个符号，则该表有符号，则该表有n+1列列)，第一列记为，第一列记为I，第，第二、三列分别记为二、三列分别记为Ia,Ib。第23页，本讲稿共74页置该表的第一行第一列为置该表的第一行第一列为 _closure(Q0)，即一列包含即一列包含M初态集初态集Q0的的_闭包。然后计闭包。然后计算它的算它的Ia和和Ib,分别填入第二、三列上，一分别填入第二、三列上，一般，若某一行的第一列上的般，若某一行的第一列上的I已确
18、定，便可已确定，便可根据前述定义求出这一行的第二、第三列根据前述定义求出这一行的第二、第三列上的上的Ia和和Ib。检查检查Ia和和Ib，看它们是否已在表的第一列，看它们是否已在表的第一列中出现，把未曾出现者之一填入下一空行中出现，把未曾出现者之一填入下一空行的第一列上，再计算该行的第二、第三列的第一列上，再计算该行的第二、第三列上的上的Ia和和Ib。第24页，本讲稿共74页重复第二步，直至表中所有第二、第三列重复第二步，直至表中所有第二、第三列上的元素全部再第一列出现为止。上的元素全部再第一列出现为止。因为因为M中的状态中的状态(子集子集)的个数是有限的，所的个数是有限的，所以上述三步必定在有
19、限步骤内终止。以上述三步必定在有限步骤内终止。将由上述过程得到的最终形式的表看作一将由上述过程得到的最终形式的表看作一个状态转换表，即把其中第一列中的元素个状态转换表，即把其中第一列中的元素作为状态，把作为状态，把Ia,Ib分别看作是输入符号分别看作是输入符号a，b，把其余信息看作是状态转换函数之值。，把其余信息看作是状态转换函数之值。这个表唯一地刻画了一个确定的有穷状态这个表唯一地刻画了一个确定的有穷状态自动机自动机M，其初态是该表第一行第一列的，其初态是该表第一行第一列的元素，其终态是该表中所有那些含有原终元素，其终态是该表中所有那些含有原终态的元素。可以证明，这个态的元素。可以证明，这个
20、DFAM 和和NFAM是等价的。是等价的。第25页，本讲稿共74页例：有一例：有一NFAM，用造表法使其确定化。，用造表法使其确定化。bbaab01253467891001234bbbbbaaaaa第26页，本讲稿共74页3.2.5确定的有穷自动机的化简确定的有穷自动机的化简 n所谓一个确定的有穷自动机所谓一个确定的有穷自动机M的化简是指：的化简是指：寻找一个状态数比寻找一个状态数比M少的少的DFAM，使得使得L(M)=L(M)，可通过消除多余状态和合并，可通过消除多余状态和合并等价状态而转换成一个最小的与之等价的等价状态而转换成一个最小的与之等价的有穷自动机。有穷自动机。n消除多余状态消除多
21、余状态多余状态是指从该自动机的开始状态出发，多余状态是指从该自动机的开始状态出发，任何输入串也不能到达的状态。任何输入串也不能到达的状态。第27页，本讲稿共74页ABC第28页，本讲稿共74页3.2.6合并等价状态合并等价状态 n等价状态等价状态若若s和和t是是M的两个不同状态，称的两个不同状态，称s和和t等等价：如果从状态价：如果从状态s出发能读出某个字出发能读出某个字 而停而停于终态，同样从于终态，同样从t出发也能读出同一个字出发也能读出同一个字 而停于终态；反之若从而停于终态；反之若从t出发能读出某个字出发能读出某个字 而停于终态，则从而停于终态，则从s出发也能读出同一个出发也能读出同一
22、个字字 而停于终态。而停于终态。n如果如果DFAM的两个状态的两个状态s和和t不等价，则称不等价，则称这两个状态是可区别的。这两个状态是可区别的。第29页，本讲稿共74页lDFA中，状态中，状态s和和t等价的条件是：等价的条件是：一致性条件：状态一致性条件：状态s和和t必须同时为可接受必须同时为可接受状态状态(终态终态)或不可接受状态或不可接受状态(非终态非终态)。蔓延性条件：对于所有输入符号，状态蔓延性条件：对于所有输入符号，状态s和和t必须转换到等价的状态里。必须转换到等价的状态里。l分割法合并等价状态分割法合并等价状态一个一个DFAM的状态化简过程就是把的状态化简过程就是把M的状态集划分
23、成一些不相交的子集，使得的状态集划分成一些不相交的子集，使得任何不同的两子集的状态都是可区分的，任何不同的两子集的状态都是可区分的，而同一子集的任何两个状态都是等价的。而同一子集的任何两个状态都是等价的。最后，从每个子集选出一个代表最后，从每个子集选出一个代表(代表该子代表该子集集)，同时消去其它等价状态。，同时消去其它等价状态。第30页，本讲稿共74页l对对M的状态集的状态集S进行划分的步骤：进行划分的步骤：把把S的终态与非终态分开，分成两个子集，的终态与非终态分开，分成两个子集，形成基本划分形成基本划分，属于这两个不同子集的状，属于这两个不同子集的状态是可区别的。态是可区别的。假定某个时候
24、假定某个时候 已含已含m个子集，记个子集，记=I(1),I(2),I(m)且属于不同子集的状态是可且属于不同子集的状态是可区别的，再检查区别的，再检查 中的每个中的每个I能否进一步划能否进一步划分，对于某个分，对于某个I(i)，令，令I(i)=S1,S2,Sk，若存在一个输入字符使得若存在一个输入字符使得move(I(i),a)不包不包含在现行含在现行 的某一子集的某一子集I(i)中，则将中，则将I(i)一分一分为二。为二。第31页，本讲稿共74页例：将图示的例：将图示的DFAM最小化。最小化。1362457aaaaaaabbbbbbb第32页，本讲稿共74页1、将、将M状态分为两个子集：状态
25、分为两个子集：P0=(1,2,3,4,5,6,7)2、1,2,3,4读入读入a后划为：后划为：P1=(1,2,3,4,5,6,7)3、进一步划分：进一步划分：P2=(1,2,3,4,5,6,7)4、考察考察5,6,7,将将P2划分为：划分为：P3=(1,2,3,4,5,6,7)P3不可再划分，从而不可再划分，从而1与与2，6与与7等价。等价。第33页，本讲稿共74页13645aaabbbbba第34页，本讲稿共74页3.2.7从化简后的从化简后的DFA到程序表示到程序表示 n识别标识符的识别标识符的DFA（见图（见图(a)）需改为图）需改为图(b)所示状态，其中，所示状态，其中，l代表字母，代
26、表字母，d代表数代表数字。字。图图(a)图图(b)第35页，本讲稿共74页l如果赋予状态如果赋予状态q0、q1与与q2一定的操作，则一定的操作，则可得识别单词标识符的程序流程图可得识别单词标识符的程序流程图(见下图见下图)。第36页，本讲稿共74页3.3正规文法与有穷自动机正规文法与有穷自动机正规文法与有穷自动机正规文法与有穷自动机FA有着特殊的有着特殊的关系。可以证明：对任何正规文法关系。可以证明：对任何正规文法G，可以，可以构造一个构造一个FA，它能而且只能识别语言，它能而且只能识别语言L(G)；反过来，对任何；反过来，对任何FA，可以构造一个相应，可以构造一个相应的正规文法的正规文法G，
27、它能生成由该，它能生成由该FA所识别的语所识别的语言。言。第37页，本讲稿共74页2.3.1从正规文法到从正规文法到FA n设正规文法设正规文法G有形如有形如UaV(a VT,V VN或或V=)的产生式。由正规文法的产生式。由正规文法G可以直可以直接构造一个有穷自动机接构造一个有穷自动机A(简称自动机简称自动机A)，使使L(A)=L(G)。构造步骤如下：。构造步骤如下：令正规文法令正规文法G的终结符号集作为有穷自动的终结符号集作为有穷自动机机A的字母表；的字母表；文法文法G的每一个非终结符都作为自动机的每一个非终结符都作为自动机A的一个状态，特别是文法的一个状态，特别是文法G的开始符作为的开始
28、符作为自动机自动机A的开始状态；的开始状态；第38页，本讲稿共74页在自动机在自动机A中增加一个新状态中增加一个新状态z作为自动作为自动机的终止状态；机的终止状态；对于文法对于文法G的形如的形如UaV(a VT或或a=,V VN)的产生式，在自动机的产生式，在自动机A中构造中构造形如形如t(U,a)=V的映射；的映射；对文法对文法G的形如的形如Ua(a VT)的产生式，的产生式，在自动机在自动机A中构造形如中构造形如t(U,a)=z的映射。的映射。第39页，本讲稿共74页2.3.2从从FA到正规文法到正规文法n从自动机也可直接构造其正规文法。构造从自动机也可直接构造其正规文法。构造步骤如下：步
29、骤如下：自动机每一个状态的标记，均作为正规文自动机每一个状态的标记，均作为正规文法的非终结符，其中，自动机开始状态的法的非终结符，其中，自动机开始状态的标记将作为正规文法的开始符号。自动机标记将作为正规文法的开始符号。自动机的输入字母表中的所有符号，作为正规文的输入字母表中的所有符号，作为正规文法的终结符。法的终结符。第40页，本讲稿共74页对于自动机的映射对于自动机的映射t(U,a)=V（其中，（其中，U、V为自动机的状态标记；为自动机的状态标记；a为输入符号），为输入符号），构造文法的一条产生式构造文法的一条产生式UaVU、V为文法的非终结符，为文法的非终结符，a为终结符。为终结符。对于自
30、动机的终止状态对于自动机的终止状态Z，在正规文法中，在正规文法中增加一条产生式增加一条产生式Z 第41页，本讲稿共74页3.4 正规表达式与正规表达式与FA 正规式也称正规则式、正规表达式，与正规正规式也称正规则式、正规表达式，与正规文法的功能一样，正规式也可用以描述程序设计文法的功能一样，正规式也可用以描述程序设计语言的单词符号。语言的单词符号。3.4.1 正规表达式的操作符正规表达式的操作符l连接连接 假定有两个正规表达式假定有两个正规表达式e1和和e2，它们分别，它们分别产生语言产生语言L1和和L2，于是定义正规表达式的连接，于是定义正规表达式的连接操作为操作为 e1 e2=x y|x
31、L1，y L2 其中其中 可省略可省略第42页，本讲稿共74页l选择选择可用可用|或或+表示，定义为表示，定义为e1|e2=x|x L1或或x L2l重复重复用用*表示，表示表示，表示*中的表达式的中的表达式的0次到若干次次到若干次的自重复连接，即的自重复连接，即e*=x|x L1*第43页，本讲稿共74页例：例：正规表达式正规表达式110由数字由数字1，1，0连接在一起组成，连接在一起组成，且表示的语言为且表示的语言为L=110表达式表达式0|1所表示的语言为所表示的语言为L=0，1表达式表达式1*所表示的语言为所表示的语言为L=1i|i=0，1，2.例：用正则表达式表示例：用正则表达式表示
32、标识符标识符=字母字母(字母字母|数字数字)*实数实数=(e|+|-)(数字数字*.数字数字 数字数字*)第44页，本讲稿共74页3.4.2正规表达式的定义正规表达式的定义n所有正规表达式都可以由下列规则构造出来：所有正规表达式都可以由下列规则构造出来：是一个表示空集的正规表达式是一个表示空集的正规表达式 是一个正规表达式，它所表示的语言仅是一个正规表达式，它所表示的语言仅包含一个空符号串，即包含一个空符号串，即 a是一个正规表达式，是一个正规表达式，a VT它所表示的语它所表示的语言（它所表示的正规集）是单个符号言（它所表示的正规集）是单个符号a所组所组成，即成，即a第45页，本讲稿共74页
33、如果如果e1和和e2是正规表达式，其表示的语言分是正规表达式，其表示的语言分别为别为L1和和L2，(e1)|(e2)是一个表示语言是一个表示语言L1 L2的正规表达式的正规表达式(e1)(e2)是一个表示语言是一个表示语言L1L2的正规表达式的正规表达式(e1)*是一个表示语言是一个表示语言L1*的正规表达式的正规表达式正规表达式中操作符的优先级顺序为正规表达式中操作符的优先级顺序为*，连接，连接，|第46页，本讲稿共74页例：例：n正规表达式正规表达式a*b*表示的正规集是表示的正规集是ambn|m 0,n 0n正规表达式正规表达式(ab)*表示的正规集是表示的正规集是(ab)m|m 0n正
34、规表达式正规表达式(a|b)*表示的正规集是表示的正规集是x|x a,b*n表达式表达式(aa|ab|ba|bb)*表示在表示在VT=a,b上的所有偶长度的串上的所有偶长度的串第47页，本讲稿共74页3.4.3正规表达式的等价性正规表达式的等价性n如果两个正规表达式表示相同的语言，则这如果两个正规表达式表示相同的语言，则这两个正规表达式相等或等价，故有两个正规表达式相等或等价，故有00*=000*|03.4.4正规表达式的性质正规表达式的性质nr|s=s|r或满足交换律或满足交换律nr|(s|t)=(r|s)|t或满足结合律或满足结合律n(rs)t=r(st)连接满足结合律连接满足结合律nr(
35、s|t)=rs|rt(s|t)r=sr|tr分配律分配律n r=r，r=r 是连接的恒等元素是连接的恒等元素第48页，本讲稿共74页例：程序设计语言中的单词都能用正规式来例：程序设计语言中的单词都能用正规式来定义，如：定义，如：n=字母字母,数字数字上的正规式上的正规式e1=字母字母(字母字母|数数字字)*表示的是所有标识符的集合表示的是所有标识符的集合n正规式正规式e=dd*定义了无符号整数定义了无符号整数n令令=d,.,e,+,-，则则 上的正规式上的正规式(d*.dd*|dd*)(e(+|-|)dd*|)表示的是无符表示的是无符号数。号数。第49页，本讲稿共74页3.4.5正规文法与正规
36、式正规文法与正规式 一个正规语言可以由正规文法定义，也一个正规语言可以由正规文法定义，也可以由正规式定义，对任意一个正规文法，可以由正规式定义，对任意一个正规文法，存在一个定义同一个语言的正规式；反之，存在一个定义同一个语言的正规式；反之，对每个正规式，存在一个生成同一语言的正对每个正规式，存在一个生成同一语言的正规文法。规文法。n正规式转换成正规文法正规式转换成正规文法将将 上的一个正规式转换成文法上的一个正规式转换成文法G=(VN,VT,P,S)，令其中的，令其中的VT=，确定产生，确定产生式和式和VN的元素用如下方法：的元素用如下方法：第50页，本讲稿共74页对任何正规式对任何正规式r，
37、选择一个非终结符，选择一个非终结符S，生，生成产生式成产生式Sr，并将，并将S定为定为G的识别符号。的识别符号。若若x和和y都是正规式，对形如都是正规式，对形如Axy的产生的产生式，重写为式，重写为AxB，By两产生式，其中两产生式，其中B是新选择的非终结符，即是新选择的非终结符，即B VN。对已转换的文法中的形如对已转换的文法中的形如Ax*y的产生式，的产生式，重写为重写为AxA,Ay对形如对形如Ax|y的产生式重写为的产生式重写为Ax，Ay不断利用上述规则作变换，直到每个产生不断利用上述规则作变换，直到每个产生式最多含有一个式最多含有一个VN为止。为止。第51页，本讲稿共74页例：将例：将
38、R=a(a|d)*转换成相应的正规文法。转换成相应的正规文法。令令S是识别符号，首先形成是识别符号，首先形成Sa(a|d)*，下一步，下一步，SaA,A(a|d)*，重写为：，重写为：A(a|d)A，A进而转变为：进而转变为：SaA，AaA，AdA，A第52页，本讲稿共74页l正规文法转换成正规式正规文法转换成正规式上述过程的逆过程，最后只剩下一个开上述过程的逆过程，最后只剩下一个开始符号定义的产生式，并且该产生式的始符号定义的产生式，并且该产生式的右部不含非终结符，转换规则：右部不含非终结符，转换规则：第53页，本讲稿共74页例：文法例：文法GS：SaA，Sa，AaA，AdA，Aa，AdS=
39、aA|a，A=aA|dA|a|d=(a|d)A|(a|d)A=(a|d)*(a|d)S=a(a|d)*(a|d)|a=a(a|d)*(a|d)|)=a(a|d)*练习：有文法练习：有文法GS：SaS，SaB，BbC，CaC，Ca第54页，本讲稿共74页3.4.6正规式和有穷自动机的等价性正规式和有穷自动机的等价性n正规表达式与有穷自动机等价，是指若给定正规表达式与有穷自动机等价，是指若给定一正则表达式，也即相应地给定了正则集合一正则表达式，也即相应地给定了正则集合L(e)，那么就可构造，那么就可构造NFAM，并有，并有L(M)=L(e)；反之，若给定一个；反之，若给定一个DFAM，M接受的接受
40、的语言为语言为L(M)，则必然存在一正则表达式，则必然存在一正则表达式e，且且L(e)=L(M)。n正规表达式和正规表达式和FA是定义语言（符号串集）是定义语言（符号串集）的两种不同形式。同一个语言，既可用的两种不同形式。同一个语言，既可用FA描述，也可用正规表达式描述。描述，也可用正规表达式描述。第55页，本讲稿共74页3.4.7正规表达式到正规表达式到NFA的转换的转换n先构造一个先构造一个NFAM的一个广义转换图，其的一个广义转换图，其中，只有中，只有S与与Z两个状态，两个状态，S是开始状态，是开始状态，Z是终止状态，弧上是正规表达式是终止状态，弧上是正规表达式e。然后，。然后，按照下图
41、所示的替换规则对正规表达式按照下图所示的替换规则对正规表达式e逐逐步进行分解，直到转换图中所有的弧上都是步进行分解，直到转换图中所有的弧上都是S中的单个符号或中的单个符号或e为止。为止。第56页，本讲稿共74页替换成替换成替换成替换成替换成替换成第57页，本讲稿共74页例：有例：有=a,b上的正规式上的正规式R=(a|b)*abb，构造，构造NFA M使使L(M)=L(e)。练习：构造与练习：构造与=a,b上的正规式上的正规式(a|b)*(aa|bb)(a|b)*等价的自动机。等价的自动机。第58页，本讲稿共74页3.4.8NFA到正规表达式的转换到正规表达式的转换n一个输入字母表为一个输入字
42、母表为 的的NFAM，可构造正规，可构造正规表达式表达式e，使，使L(e)=L(M)。具体操作如下：。具体操作如下：首先对首先对NFAM进行拓广，在进行拓广，在M的状态转换的状态转换图中，设置一个唯一的开始状态图中，设置一个唯一的开始状态S和唯一的和唯一的终止状态终止状态Z，并允许状态转换图中弧上可以，并允许状态转换图中弧上可以为正规表达式。为正规表达式。然后从开始状态然后从开始状态S到原来所有的开始状态到原来所有的开始状态连接连接 弧，再从原来所有的终止状态到弧，再从原来所有的终止状态到Z状状态也连接态也连接 弧。修改后构成了一个新的弧。修改后构成了一个新的NFA，它只有一个初态结点，它只有
43、一个初态结点S和一个终态结点和一个终态结点Z，这个新的，这个新的NFAM显然和原显然和原NFAM等价。等价。第59页，本讲稿共74页接着，利用下图所示的替换规则，逐步消接着，利用下图所示的替换规则，逐步消去去M中属于中属于M的所有结点和有关连线，直到的所有结点和有关连线，直到状态转换图中只剩下状态状态转换图中只剩下状态S和和Z为止为止(这个过这个过程称为消结程称为消结)。在消结过程中，用相应的正。在消结过程中，用相应的正规表达式标记连线。规表达式标记连线。第60页，本讲稿共74页替换成替换成替换成替换成替换成替换成第61页，本讲稿共74页例：例：NFAM=(0,1,2,3,4,a,b,f,0,
44、2,4),状状态图如下，构造正规式态图如下，构造正规式R使使L(R)=L(M)。03412aabba,ba,ba,b第62页，本讲稿共74页3.5 DFA在计算机中的表示在计算机中的表示 l矩阵表示法矩阵表示法设设M是一个二维数组，若是一个二维数组，若t(qi,qj)=qk，则令，则令Mi,j=k，其中，其中i,k=0,1,2,n；j=1,2,m。l表结构表结构 DFA的映射的映射t:QQ在计算机中可表示成在计算机中可表示成一种表结构。在这个表结构中，每一个状态对一种表结构。在这个表结构中，每一个状态对应一个表，表中包括该状态的状态名、从该状应一个表，表中包括该状态的状态名、从该状态发出的弧数
45、、每条弧上的标记以及弧达到的态发出的弧数、每条弧上的标记以及弧达到的状态所在表的首地址。状态所在表的首地址。第63页，本讲稿共74页DFA在计算机中的表结构在计算机中的表结构 第64页，本讲稿共74页l程序表示法程序表示法我们也可以用程序来表示我们也可以用程序来表示DFA。例：例：C语言的注释语言的注释/*/，其有穷自动机，其有穷自动机12345/*/*otherother第65页，本讲稿共74页State 1if the next characterr is“/”then advance the input;State 2 if the next character is“*”then ad
46、vance the input;State 3 done:=false;while not done do while the next input character is not“*”do advance the input;end while;advance the input;State 4第66页，本讲稿共74页while the next input character is“*”do advance the input;end while;if the next input character is“/”then done:=true;end if;advance the inp
47、ut;end while;accept;State 5 else other processing end ifelse other processing end if State:=1;Start 第67页，本讲稿共74页while state=1,2,3 or 4 do case state of 1:case input character of “/”:advance the input state:=2;else state:=Error or Other end case 2:case input character of “*”:advance the input;state:=
48、3;else state=.Error or Other end case 第68页，本讲稿共74页 3:case input character of“*”:advance the input;state:=4;else advance the inputand stay in State 3 end case 4:case input character of “/”:advance the input;state:=5;“*”:advance the input;and stay in State 4 else advance the input;state:=3;end case en
49、d caseend whileif state=5 then accept else error第69页，本讲稿共74页本章小结本章小结 1、自动机是一种能进行运算并能实现自我控、自动机是一种能进行运算并能实现自我控制的装置。它是描述符号串处理的强有力的工具，制的装置。它是描述符号串处理的强有力的工具，是研究扫描器的理论基础。有穷自动机是研究扫描器的理论基础。有穷自动机(FA)分为确分为确定有穷自动机定有穷自动机(DFA)和非确定有穷自动机和非确定有穷自动机(NFA)。2、DFA=(Q，t，q0，F)，Q是状态集，是状态集，是输入字母表，是输入字母表，t：QQ，q0 Q是开始状态，是开始状态，
50、F Q是终止状态集。是终止状态集。第70页，本讲稿共74页 3、NFA=(Q，t，Q0，F)，t：QQ的子集，的子集，Q0 Q是开始状态集。是开始状态集。4、对、对NFA可采用子集法和造表法进行确定可采用子集法和造表法进行确定化，将其转化为等价的化，将其转化为等价的DFA。对。对 DFA则可进行则可进行最小化最小化(化简化简)，对，对DFA化简的基本思想是将状态集化简的基本思想是将状态集分解成若干个互不相交的子集，使每个子集中的状分解成若干个互不相交的子集，使每个子集中的状态都是等价的，而不同子集的状态是可区分的。态都是等价的，而不同子集的状态是可区分的。本章小结本章小结第71页，本讲稿共74