计算理论第2章有限自动机和正规文法

第二章第二章 有限自动机和正规文法有限自动机和正规文法2.1 确定的有限自动机确定的有限自动机(DFA)DFA)(DeterminateFiniteAutomaton)有限自动机是研究自动系统的一种数学模型，它出现有限自动机是研究自动系统的一种数学模型，它出现于本世纪四十年代。于本世纪四十年代。1943年由年由McCulloch与与Pitts建立了模拟神经网络的自动机建立了模拟神经网络的自动机,1956年由年由Moore建立了描述计算机的时序机的概念。建立了描述计算机的时序机的概念。以后自动机的理论日趋发展，并且与计算机的信息处理以后自动机的理论日趋发展，并且与计算机的信息处理密切结合，它不仅用于研究计算机的结构，还用于研究密切结合，它不仅用于研究计算机的结构，还用于研究形式语言形式语言语言的识别。语言的识别。在这里主要是从识别语言这方面来研究自动机。在这里主要是从识别语言这方面来研究自动机。一一.有限自动机有限自动机(FA)的结构的结构有限自动机由三部分构成：有限自动机由三部分构成：1.输入带输入带输入带可以任意长，带上输入带可以任意长，带上有若干单元，每个单元内有若干单元，每个单元内有输入符号。输入带上存有输入符号。输入带上存放的是被有限自动机识别放的是被有限自动机识别的符号串。如图所示，的符号串。如图所示，输入带上的符号串为：输入带上的符号串为：a1a2a3an。2.读头读头读头是将输入带上的符号读到有限控制器中，每次读读头是将输入带上的符号读到有限控制器中，每次读一个单元的符号。一个单元的符号。有有限限控控制制器器a1a2a3 an输入带输入带读头读头3.有限控制器有限控制器 有限控制器是有限自动机的核心。有限控制器是有限自动机的核心。有限自动机有多个状态，有一个开始状态，还有限自动机有多个状态，有一个开始状态，还有若干个终止状态。有若干个终止状态。自动机每读带上一个符号自动机每读带上一个符号,状态可能发生变化，状态可能发生变化，然后读头右移一个单元。然后读头右移一个单元。自动机如何从开始状态出发，识别完带上的整自动机如何从开始状态出发，识别完带上的整个符号串后，要进入某个终止状态，这个过程就个符号串后，要进入某个终止状态，这个过程就是由有限控制器控制的。是由有限控制器控制的。二二.确定的有限自动机确定的有限自动机(DFA)的形式描述的形式描述定义定义：确定的有限自动机：确定的有限自动机M写成有序五元组，记写成有序五元组，记作作M=(K,q0,F)其中，其中，K有限自动机的状态的有限集合。有限自动机的状态的有限集合。输入带上的有穷字母表。输入带上的有穷字母表。状态转移函数状态转移函数,是是KK的映射。的映射。例如，例如，(q,a)=p(其中其中q,pK,a),表示在表示在q状态下，读状态下，读a后，状态改为后，状态改为p,然后，将读头右移然后，将读头右移一个单元。一个单元。q0开始状态开始状态q0KF终止状态集合，终止状态集合，F K三三.确定的有限自动机的表示方法确定的有限自动机的表示方法【例【例2-1.1】给定确定的有限自动机给定确定的有限自动机M=(K,q0,F)K=q0,q1,q2,q3,=0,1,F=q0:(q0,0)=q2(q0,1)=q1(q1,0)=q3(q1,1)=q0(q2,0)=q0(q2,1)=q3(q3,0)=q1(q3,1)=q2状态转移函数状态转移函数也可以也可以用函数表表示用函数表表示，如上表所示。，如上表所示。0 10 1q0q2q1q1q3q0q2q0q3q3q1q2aq(q,a)=q(c)qq F(d)q q0 0开始状态开始状态q0(a)q q p p(q,a)=p(b)a有限自动机还可以有限自动机还可以用图表示用图表示。方法如下：。方法如下：四状态转移函数四状态转移函数定义的扩充定义的扩充原原：KK的映射。的映射。1100q0q1q2q311000 10 1q0q2q1q1q3q0q2q0q3q3q1q2(q,)=qM M的状态转移图的状态转移图:为描述有限自动机为描述有限自动机M接收的语言，将接收的语言，将函数扩充成函数扩充成：K*K的映射。对于任何的映射。对于任何x*，如果如果一般地表示：一般地表示：(q,x)=p,表示在状态表示在状态q下，读下，读符号串符号串x后，到状态后，到状态p。(q,xa)=(q,x),a)其中其中x*，a 例如上例中例如上例中(q0,010)=(q0,01),0)=(q0,0),1),0)(q2,1),0)=(q3,0)=q1。(q0,),0),1),0)=(q0,0),1),0)但此时的但此时的一定理解成一定理解成。(q0,010)=q1也可以写成也可以写成(q0,010)=q1。造成混淆，所以造成混淆，所以起见，符号起见，符号与与可以不作区分地使用，这样做也不会可以不作区分地使用，这样做也不会可见在确定的有限自动机中，可见在确定的有限自动机中，是由是由定义的定义的,为了简单为了简单五确定的有限自动机M接收的语言T(M)给定确定的有限自动机给定确定的有限自动机M=(K,q0,F)，M接收的接收的语言语言T(M)为：为：T(M)=w|w*且且(q0,w)=p其中其中pF例例2-1.1中，中，T(M)=?1100q0q1q2q31100T(M)=w|w0,1*且且w中中0或者或者1的个数均为偶数的个数均为偶数。作业题作业题1设设计计一一个个有有限限自自动动机机(FA)M，使使得得T(M)中中的的每每个个句句子子w同同时时满满足足下下面面三三个个条件：条件：1)wa,b,*；2)|w|是是3的整数倍；的整数倍；3)w以以a开头，以开头，以b结尾。结尾。2设计二个设计二个FAM1和和M2，分别满足分别满足T(M1)=02i i是自然数是自然数T(M2)=02i+1 i=0,1,2,3,4,2.2 不确定的有限自动机（不确定的有限自动机（NFA）(Non-deterministic Finite Automaton)DFA是在每个状态下，读一个符号后的下一个状态是是在每个状态下，读一个符号后的下一个状态是唯一确定的，下面讨论的有限自动机是在某个状态下，唯一确定的，下面讨论的有限自动机是在某个状态下，读一个符号后的下一个状态可能不是唯一确定的，这就读一个符号后的下一个状态可能不是唯一确定的，这就是不确定的有限自动机。是不确定的有限自动机。一一.不确定的有限自动机（不确定的有限自动机（NFA）的形式定义的形式定义定义定义：不确定的有限自动机：不确定的有限自动机M，用一个有序五元组表示：用一个有序五元组表示：M=(K,q0,F)其中，其中，K、q0、F的含义同的含义同DFA。状态转移函数状态转移函数,是是K2K的映射。的映射。例例.(q,a)=p,s(q,a)=p,s(其中其中qK,p,sqK,p,s2K a)a)【例【例2-2.1】.给定给定NFAM，M=(K,q0,F)其中，其中，K=q0,q1,q2,q3,q4=0,1F=q2,q4：K2K为：为：01q0q0,q3q0,q1q1q2q2q2q2q3q4q4q4q4q0q1q2q3q40,10,10,10011图图2-2.1 NFA MNFA M状态转移图状态转移图二二.状态转移函数状态转移函数定义的扩充定义的扩充原来原来：K2K，下面对它进行下面对它进行两次扩充两次扩充。与确。与确定的有穷自动机相类似，定的有穷自动机相类似，扩充以后的状态转移函数仍扩充以后的状态转移函数仍然用然用。因为这样做。因为这样做,在计算时也不会引起错误。在计算时也不会引起错误。1.将将扩充成：扩充成：K*2K，定义为：定义为：x*,(q,x)=p1,p2,pn（p1,p2,pn2K）表示在状态表示在状态q下下,读读符号串符号串x后后,可以达到状态可以达到状态pi(1in)。一般地表示：一般地表示：(q,)=qqK(q,xa)其中其中qK,x*，a(q0,01)=(q0,1)(q3,1)=q0,q1=q0,q1例例2-2.1中中(q0,0)=q0,q3,则则为了计算为了计算(q,xa)方便，方便，2.将将的定义再一次扩充成：的定义再一次扩充成：2K2K，对于任何对于任何Pp1,p2,pn2K，a(2)(q,xa)=(q,x),a)即即(P,a)等于等于P中每个状态分别读中每个状态分别读a后状态集合的并集。后状态集合的并集。的定义经过扩充之后，计算的定义经过扩充之后，计算(q,xa)的式子可写成：的式子可写成：(q,xa)=(q,x),a)。于是对于任何于是对于任何x*,a(1)(q,)=qqK(P,a)=(p1,p2,pn,a)=三三.NFAM所接收的语言所接收的语言T(M)给定给定NFAM=(K,q0,F),M所接收的语言所接收的语言T(M)为：为：T(M)=w|w*且且(q0,w)F例例2-2.1中，中，T(M)=?T(M)=w|w0,1*且且w中或者有两个相邻的中或者有两个相邻的0或者有两或者有两个相邻的个相邻的1q0q1q2q3q40,10,10,10011图图2-2.1 NFA MNFA M状态转移图状态转移图四四NFA转换成转换成DFA任何一个任何一个NFA都可以等价地转换成都可以等价地转换成DFA。定理定理2-2.1如果语言如果语言L可由一个可由一个NFAM所接收，则必存所接收，则必存在一个在一个DFAM，使得使得T(M)=L。证明证明：令：令NFAM=(K,q0,F)，且且T(M)=L。构造构造DFAM=(K,q0,F),其中其中K 2K，K中的元素是由中的元素是由K的子集的子集q1,q2,qi构成，但构成，但是要把子集是要把子集q1,q2,qi作为一个状态看待，因此把此作为一个状态看待，因此把此子集写成子集写成q1,q2,qi。q0=q0,F=q1,q2,qi|q1,q2,qiK且且q1,q2,qiF：KK，对对 q1,q2,qiK,a，有有(q1,q2,qi,a)=p1,p2,pj当且仅当当且仅当(q1,q2,qi,a)=p1,p2,pj这说明：计算这说明：计算时，完全取决于时，完全取决于NFA中中（注注：为了更好地理解如何根据：为了更好地理解如何根据NFAM构造构造DFAM，可可以先看例子，然后再看下面的证明，这样更容易理解证以先看例子，然后再看下面的证明，这样更容易理解证明的过程。）明的过程。）例例.将例将例2-2.12-2.1中的中的NFA MNFA M等价变换成等价变换成DFA MDFA M。按照上述按照上述定定理给定的方法。令理给定的方法。令MM(K,q0,F)，其中，其中，K、F:因因为为K 2K，在在求求K时时，不不需需要要将将2K中中的的所所有有元元素素都都列列入入K,只需要列入只需要列入从开始状态从开始状态q0可以达到的状态即可可以达到的状态即可,为为此可以先求此可以先求，然后得到，然后得到K和和F。例例2-2.1：NFAM=(K,q0,F)其中，其中，K=q0,q1,q2,q3,q4=0,1F=q2,q4构造构造DFAM=(K,q0,F),q0=q0:q1,q2,qiK,a,有有(p1,p2,pj,a)=q1,q2,qn当且仅当当且仅当(p1,p2,pj,a)=q1,q2,qn从从q0开始，计算各个可达状态的转移函数。开始，计算各个可达状态的转移函数。例如例如要计算要计算(q0,q3,0)首先计算首先计算(q0,q3,0)。(q0,q3,0)=(q0,0)(q3,0)=q0,q3q4=q0,q3,q4,于是于是(q0,q3,0)=q0,q3,q4,其余的依此类推。其余的依此类推。最后得下表最后得下表01q0q0,q3q0,q1q1q2q2q2q2q3q4q4q4q4:K=q0,q0,q3,q0,q1,q0,q3,q4,q0,q1,q2,q0,q2,q3,q0,q1,q4,q0,q2,q3,q4,q0,q1,q2,q4,F=q0,q3,q4,q0,q1,q2,q0,q2,q3,q0,q1,q4,q0,q2,q3,q4,q0,q1,q2,q4 0 1 0 1 q0q0,q3q0,q1q0,q3q0,q3,q4q0,q1q0,q1q0,q3q0,q1,q2q0,q3,q4q0,q3,q4q0,q1,q4q0,q1,q2q0,q2,q3q0,q1,q2q0,q2,q3q0,q2,q3,q4q0,q1,q2q0,q1,q4q0,q3,q4q0,q1,q2,q4q0,q2,q3,q4q0,q2,q3,q4q0,q1,q2,q4q0,q1,q2,q4q0,q2,q3,q4q0,q1,q2,q4：01q0q0,q3q0,q1q1q2q2q2q2q3q4q4q4q4:M的图：的图：q0 q0,q1 1 11 11 11 11 11 11 11 11 10 00 00 00 00 00 00 00 00 0 q0,q1,q2 q0,q3,q4 q0,q2,q3 q0,q1,q4 q0,q2,q3,q4 q0,q1,q2,q4 图图2-2.2M的状态转移图的状态转移图 q0,q3 证明证明：T(M)=T(M)1.先用归纳法证明先用归纳法证明(对输入符号串对输入符号串|x|归纳归纳)下面命题成立：下面命题成立：对于任何对于任何x*，(q0,x)=q1,q2,qn当且仅当当且仅当(q0,x)=q1,q2,qn(1)当当|x|=0，即即x=时，时，(q0,)=q0=q0当且仅当当且仅当(q0,)=q0，命题成立。命题成立。(2)假设假设|x|k时，命题成立。即时，命题成立。即(q0,x)=p1,p2,pj当且仅当当且仅当(q0,x)=p1,p2,pj(3)当当|xa|=k+1时，时，a,有有(q0,xa)=(q0,x),a)(q0,xa)=(q0,x),a)因为因为|x|=k,由假设由假设(2)得得(q0,x)=p1,p2,pj当且仅当且仅当当(q0,x)=p1,p2,pj。故故(q0,xa)=(p1,p2,pj,a)当且仅当当且仅当(q0,xa)=(p1,p2,pj,a)，所以命题成立。所以命题成立。2.再证明再证明T(M)=T(M)对于任何对于任何x*,如果如果xT(M)，则则(q0,x)F，令令(q0,x)=p1,p2,pj，即即p1,p2,pjF。因命题因命题(q0,x)=p1,p2,pj当且仅当当且仅当(q0,x)=p1,p2,pj成立。成立。由由F定义得定义得p1,p2,pjF当且仅当当且仅当p1,p2,pjF，即即(q0,x)F。于是于是xT(M)。所以所以T(M)=T(M)。定理证明完毕。定理证明完毕。从从此此定定理理看看出出:与与DFA相相比比，NFA并并没没有有扩扩大大它它所所接接收收语言的范围。语言的范围。作业题作业题给定给定NFAM1=(p,q,r,s,0,1,p,s)，如下如下表所示。构造一个表所示。构造一个DFAM2，使得使得T(M1)=T(M2)。01pp,qpqrrrssss2.3具有具有转移的转移的NFA （简记成简记成-NFA）前边讨论的前边讨论的NFA中的输入符号只是中的输入符号只是中的符号，在理中的符号，在理论上和实际应用中还有另一种论上和实际应用中还有另一种NFA，就是输入符号中除就是输入符号中除了了中的符号以外，还允许有中的符号以外，还允许有，这就是具有这就是具有转移的转移的NFA(-NFA)。【例【例2-3.1】具有具有转移的转移的NFAM(-NFAM)，如图如图2-3.1所示。从图中看出，所示。从图中看出，图中有的有向边上标有图中有的有向边上标有。q0q1q2012图图2-3.1-NFA M-NFA M图图一一-NFA的形式定义的形式定义-NFAM=(K,q0,F)，其中其中K,q0,F的含义同前边的含义同前边NFA,:K()2K例例2-3.1中的中的-NFAM的的如表如表2-3.1所示。所示。012q0q0q0,q1q1q1q2q2q2表表2-3.12-3.1-NFA M-NFA M状态转移表状态转移表q0q1q2012图图2-3.1-NFA M-NFA M图图为了讨论为了讨论-NFA接收的语言需要对接收的语言需要对的定义进行扩充。的定义进行扩充。二二的定义扩充的定义扩充先扩充成先扩充成：K*2K,定义为定义为,对于对于 qK,w*,值得注意值得注意:在在DFADFA和和NFANFA中中,对于扩充后的对于扩充后的 与与可以不加可以不加(q0,)=q0径径(即在即在0的前后可能有若干个的前后可能有若干个)，而不是输入符号而不是输入符号0。(q0,0)=q0,q1,q2(q0,0)=q0,因为这里的因为这里的0指的是指的是0路路(q0,)=q0,q1,q2(q0,)=q0,q1，因为这里的因为这里的指的是指的是路径，而不是边上标的路径，而不是边上标的。而在而在-NFA中，在例中，在例2-3.1中中(q0,0)=q0,q3=(q0,0)区别的使用，因为它们的计算结果相同。但是在这里区别的使用，因为它们的计算结果相同。但是在这里就就必须加以区别必须加以区别,因为它们的计算结果不同了。请看下例因为它们的计算结果不同了。请看下例:在在NFA中，在例中，在例2-2.1中，中，(q,w)=P=p|从从q出发，沿着标有出发，沿着标有w的的路径路径达到状态达到状态pq0q1q2012图图2-3.1-NFA M-NFA M图图为了写出为了写出(q,w)的计算公式，下面再定义两个概念。的计算公式，下面再定义两个概念。三三-CLOSURE(q)qK,-CLOSURE(q)=p|从从q出发出发,沿着沿着路径达到状态路径达到状态p上例中，上例中，-CLOSURE(q0)=q0,q1,q2,-CLOSURE(q1)=q1,q2,-CLOSURE(q2)=q2四四.-CLOSURE(P)（其中其中P是状态的集合）是状态的集合）P是状态的集合，则是状态的集合，则-CLOSURE(P)=-CLOSURE(q)上例中，上例中，-CLOSURE(q0,q1)=-CLOSURE(q0)-CLOSURE(q1)=q0,q1,q2 q1,q2=q0,q1,q2五五.对对的定义的再扩充的定义的再扩充将将的定义扩充成的定义扩充成：2K2K，注意注意,(q,wa)(q,w),a)，因路径因路径wa,是指是指w*a*,(q,wa)=-CLOSURE(q,w),a)公式公式(2)：对于对于 qK,w*,a,公式公式(1)：对于：对于 qK,(q,)=-CLOSURE(q)对对 R2K,w*,(R,w)=(r,w)再扩充成再扩充成：2K*2K,所以要在所以要在(q,w),a)前边加前边加-CLOSURE。对对 R2K，a，(R,a)=(r,a)六六的计算公式的计算公式q0q1q2012图2-3.1-NFA M图例例如如,在在上上例例中中,计计算算(q0,01),按按照照递递归归地地定定义义公公式式(2),要要先计算：先计算：(q0,)=q0,q1,q2,再计算：再计算：(q0,0)=-CLOSURE(q0,),0)=-CLOSURE(q0,q1,q2,0)=-CLOSURE(q0,0)(q1,0)(q2,0)=-CLOSURE(q0)=-CLOSURE(q0)=q0,q1,q2最后计算最后计算(q0,01)=-CLOSURE(q0,0),1)=-CLOSURE(q0,q1,q2,1)=-CLOSURE(q0,1)(q1,1)(q2,1)=-CLOSURE(q1)=-CLOSURE(q1)=q1,q2七七.-NFAM接收的语言接收的语言T(M)给定一个给定一个-NFAM=(K,q0,F)，它接收的它接收的语言语言T(M)为：为：T(M)=w|w*且且(q0,w)F上例中上例中T(M)=0i1j2k|i,j,k0八八.-NFA等价地转换为等价地转换为NFA一个一个-NFAM可以等价地转换为没有可以等价地转换为没有转移转移的的NFA。下面介绍定理。下面介绍定理。定理定理2-3.1如果语言如果语言L由一个有由一个有转移的转移的NFAM所接收，则所接收，则L可被一个不具有可被一个不具有转移的转移的NFAM所接收。所接收。证明：证明：令一个令一个-NFAM=(K,q0,F)，它接收的语言它接收的语言T(M)为为L。构造一个不具有构造一个不具有转移的转移的NFAMM=(K,q0,F)，其中其中：对任何：对任何qK,任何任何a,(q,a)=(q,a)下面证明下面证明T(M)=T(M)。先用归纳法先用归纳法(任何任何x+，对对|x|归纳归纳)证明下面命题成立：证明下面命题成立：对于任何对于任何x+,有有(q0,x)=(q0,x),(当讨论当讨论x=时时,不不用此结论用此结论)(1)当当|x|=1时，设时，设x=a，a，根据根据的定义，有的定义，有(q0,a)=(q0,a)，命题成立。命题成立。(2)假设假设|x|k时时,命题成立。即命题成立。即(q0,x)=(q0,x)。(3).当当|xa|=k+1时，令输入符号串时，令输入符号串xa,(x+,|x|=k,a),根据归纳假设有根据归纳假设有(q0,x)=(q0,x)。因为因为(q0,xa)=(q0,x),a)，=(q0,x),a)(根据假设（根据假设（2）)=(q0,xa)综上所述，上述命题成立。综上所述，上述命题成立。=(q0,x),a)(根据根据的扩充定义的扩充定义)先证先证T(M)T(M)任取任取xT(M)，若若x，则则-CLOSURE(q0)F，由由F的构成得的构成得F=Fq0，而而(q0,)q0,所以所以(q0,)F，所以所以T(M)。若若x，则则(q0,x)F，由已经证明的命题得由已经证明的命题得(q0,x)F，由由F定义得定义得F F，所以所以(q0,x)F，所以所以xT(M)。所以所以T(M)T(M)。再证再证T(M)T(M)任取任取xT(M),下面分两种情况下面分两种情况1)如果如果x=，因因M是无是无的的NFA，必有必有(q0,)=q0 F，所以所以q0F，再分两种情况讨论再分两种情况讨论:(1)若若q0F，又有又有q0-CLOSURE(q0),所以所以-CLOSURE(q0)F,而而即即(q0,)F，所以所以T(M)。(2)若若q0 F，而而q0FF，这说明这说明FF=Fq0，即说即说明明-CLOSURE(q-CLOSURE(q0 0)F)F，即即 (q q0 0,)F F，所以所以T(M)T(M)。-CLOSURE(q0)(q0,)，2)如果如果x，分两种情况讨论分两种情况讨论(1).如果如果F=F，因为因为(q0,x)F，由上述命题知由上述命题知(q0,x)=(q0,x)，所以必有所以必有(q0,x)F，所以所以xT(M)。(2)如如果果F=Fq0，又又已已知知(q0,x)F，这这又又有有两两种种可能：可能：(a)若若q0(q0,x)，则有则有(q0,x)F(q0,x)(Fq0)(q0,x)F)(q0,x)q0)(q0,x)F)(q0,x)F即即(q0,x)F，所以所以xT(M)。(b)若若q0(q0,x)，所以所以q0(q0,x)，说明在说明在M中从中从q0出发沿着出发沿着x路径可以回路径可以回(b)若若q0(q0,x)，因为因为(q0,x)=(q0,x)，到到q0，进而也可以达到进而也可以达到-CLOSURE(q0)中的各个状态，中的各个状态，因而有因而有-CLOSURE(q0)(q0,x)，又又F=Fq0，由由F定义知定义知-CLOSURE(q0)F，于是于是(q0,x)F，所以所以(q0,x)F，所以所以xT(M)。综上所述，有综上所述，有T(M)T(M)。最后得最后得T(M)=T(M)。例例.下面将例下面将例2-3.1中的中的-NFAM等价变换成等价变换成NFAM。令令M=(K,q0,F)，其中其中K=q0,q1,q2,=0,1,2,F=q0,q2,的计算如下：的计算如下：图图2-3.2NFAM图图q0q2q10,1,22100,11,2 0 1 20 1 2 q0q0,q1,q2q1,q2q2 q1q1,q2q2 2 q2q2:(q0,0)=(q0,0)=q0,q1,q2(q0,1)=(q0,1)=-CLOSURE(q0,),1)=-CLOSURE(q0,q1,q2,1)=-CLOSURE(q0,1)(q1,1)(q2,1)=-CLOSURE(q1)=-CLOSURE(q1)=q1,q2其它的依此类推。其它的依此类推。最后得最后得的表的表2-3.2。M的图如图的图如图2-3.2所示。所示。作业题作业题将下面的将下面的-NFAM等价变换成等价变换成NFAM。abcdef10102.4正规表达式及其与有限自动机之间正规表达式及其与有限自动机之间的等价性的等价性 有限自动机所接受的语言，很容易用字母表上的符号有限自动机所接受的语言，很容易用字母表上的符号串以及符号串上的一些运算符号构成的表达式来表示，串以及符号串上的一些运算符号构成的表达式来表示，即用正规表达式来表示。即用正规表达式来表示。一一.正规表达式定义正规表达式定义设设是有限字母表，是有限字母表，上的正规表达式及其所代表的符上的正规表达式及其所代表的符号串集合递归定义如下：号串集合递归定义如下：1.是个正规表达式，它代表空集是个正规表达式，它代表空集。2.是个正规表达式，它代表集合是个正规表达式，它代表集合。3.任何任何a，是个正规表达式，它代表集合是个正规表达式，它代表集合a。4.如果如果r、s分别是代表集合分别是代表集合R、S的正规表达式的正规表达式,则则(r+s)、(rs)、(r*)分别是代表集合分别是代表集合(RS)、(RS)、(R*)的的正规表达式。正规表达式。r+s称作称作r与与s的加运算；的加运算；rs称作称作r与与s的连接运算；的连接运算；r*称作称作r的的*闭包运算。闭包运算。设设r是个正规表达式，则是个正规表达式，则r所代表的集合记作所代表的集合记作L(r)。例如例如，L()=,L(a)=a二正规表达式运算的优先级二正规表达式运算的优先级为了书写简单，看起来也简单明了，我们规定了正规为了书写简单，看起来也简单明了，我们规定了正规表达式运算的优先权，于是正规表达式的最外层的括号表达式运算的优先权，于是正规表达式的最外层的括号以及表达式里的一些括号可以省略。以及表达式里的一些括号可以省略。运算的优先权运算的优先权:从高到低依次是：从高到低依次是：*、连接、。、连接、。因此，因此，(0+(0(1*)可以简记为可以简记为001*。例如例如设设0,1，则则1.01表示集合表示集合L(01)01=012.0+1表示集合表示集合L(0+1)=L(0)L(1)=01=0,13.(0+1)*表示集合表示集合L(0+1)*)=0,1*=,0,1,00,01,10,11,000,001,4.0*表示集合表示集合L(0)*)=0*=,0,00,000,0000,5.1(0+1)*表示集合表示集合L(1(0+1)*)=10,1*=1,0,1,00,01,10,11,000,001,=1,10,11,100,101,110,111,1000,1001,三两个正规表达式相等三两个正规表达式相等设设、是是上上的的正正规规表表达达式式，如如果果L()=L(),则则称称与与相相等，记作等，记作。四四.重要的等式重要的等式（正规表达式的运算性质）（正规表达式的运算性质）、是是上的正规表达式，则上的正规表达式，则1.(+满足交换律满足交换律)2.(+满足幂等律满足幂等律)3.=(是运算的幺元是运算的幺元)4.()+(+)(+满足可结合性满足可结合性)5.(+)(连接对满足分配律连接对满足分配律)证明证明：L(+)L()L()=L()(L()L()=L()L()L()L()=L()L()=L()6.(+)7.=(是连接运算的幺元是连接运算的幺元)8.(是连接运算的零元是连接运算的零元)证明证明：L()L()L()L()=L()所以所以，类似可证类似可证9.()=()(连接运算满足可结合性连接运算满足可结合性)10.*证明证明：对任何集合：对任何集合A*A0AA2A3A4其中其中A0=,所以所以L(*)*=02=0=L()11.+*=*12.(*)*=*在离散数学中在离散数学中,二元关系二元关系R有，有，R*=rt(R)=tr(R),(R*)*=R*13.*=*=+在离散数学中，二元关系在离散数学中，二元关系R有，有，(RR*)=R*R=R+14.(+)*=*因因L(+)*)=,*=,0,1,2=,2,2,3=,23,=*=L(*)15.+=*16.()*+*=*因为因为*五五.正规表达式与有限自动机之间的等价性正规表达式与有限自动机之间的等价性下面证明有限自动机所接受的语言正好是一个正规表下面证明有限自动机所接受的语言正好是一个正规表达式所表示的语言。反之亦然达式所表示的语言。反之亦然,即任意给定正规表达式即任意给定正规表达式r,都可以确定一个都可以确定一个FAM，使得使得T(M)=L(r)。正规表达式与有限自动机之间的等价关系，可以用下面正规表达式与有限自动机之间的等价关系，可以用下面图图2-4.1表示。表示。正规表达式正规表达式NFANFADFA图图2-4.1有限自动机与正规表达式之间的等价转换关系图有限自动机与正规表达式之间的等价转换关系图定理定理2-4.1设设r是是上的一个正规表达式，则存在一个具上的一个正规表达式，则存在一个具有有转移的转移的NFAM,使得使得T(M)=L(r)。证明证明：用对：用对r中含有运算的个数归纳证明。中含有运算的个数归纳证明。1.如如果果r中中有有0个个运运算算，则则有有三三种种可可能能:r=,r=,r=aa,则则有下面三个自动机分别接受它们。有下面三个自动机分别接受它们。q0q0q1aq0q1r=r=r=r=r=ar=a2.假设假设r中运算个数少于中运算个数少于k个时，结论成立。个时，结论成立。3.当当r中有中有k个运算时，因正规表达式中只有三种运算，所个运算时，因正规表达式中只有三种运算，所以分三种情况讨论：以分三种情况讨论：(1)如果如果r=r1+r2,则则r1和和r2中运算个数少于中运算个数少于k个，由假设得，个，由假设得，存在存在NFAM1和和M2，使得使得T(M1)=L(r1)T(M2)=L(r2),不妨设不妨设M1(K1,1,1,q1,f1)M2(K2,2,2,q2,f2)设设K1K2=下面构造下面构造NFAMM(K1K2q0,f0,12,q0,f0)，其中其中q0,f0 K1K2,使得使得T(M)=T(M1)T(M2)=L(r1)L(r2)=L(r1+r2),于是于是M的结构如下图所示：的结构如下图所示：M1M2q1q2q0f1f2f0M的状态转移函数的状态转移函数为：为：(q0,)=q1,q2M可以进入可以进入M1和和M2的开始状态。的开始状态。对任何对任何qK1,任何任何a1有有(q,a)=1(q,a)M可以模拟可以模拟M1的动作。的动作。对任何对任何qK2,任何任何a2有有(q,a)=2(q,a)M可以模拟可以模拟M2的动作。的动作。(f1,)=(f2,)=f0很容易证明很容易证明T(M)=T(M1)T(M2)，这里从略。这里从略。(2).如果如果r=r1r2,则则r1和和r2中运算个数少于中运算个数少于k个个,由假设得，由假设得，存在存在NFAM1和和M2使得使得T(M1)=L(r1)T(M2)=L(r2),M1和和M2如前所述。如前所述。下面构造下面构造NFAM(K1K2,12,q1,f2)，使使得得T(M)=T(M1)T(M2)=L(r1)L(r2)=L(r1r2),于是于是M的结构如的结构如下图所示：下图所示：M1q1f1M2q2f2M的状态转移函数的状态转移函数为：为：对任何对任何qK1,任何任何a1有有(q,a)=1(q,a)M可以模拟可以模拟M1的动作。的动作。(f1,)=q2对任何对任何qK2,任何任何a2有有(q,a)=2(q,a)M可以模拟可以模拟M2的动作。的动作。很容易证明很容易证明T(M)=T(M1)T(M2)，这里从略。这里从略。(3).如果如果r=r1*,则则r1中运算个数少于中运算个数少于k个，由假设得，存个，由假设得，存在在NFAM1使得使得T(M1)=L(r1),M1如前所述。如前所述。下面构造下面构造NFAM(K1q0,f0,1,q0,f0)，使得使得T(M)=(T(M1)*=(L(r1)*=L(r1*),于是于是M的结构如下的结构如下图所示：图所示：q0M1q1f1f0M的状态转移函数的状态转移函数为：为：(q0,)=q1,f0对任何对任何qK1,任何任何a1有有(q,a)=1(q,a)M可以模拟可以模拟M1的动作。的动作。(f1,)=q1,f0下面证明下面证明T(M)=(T(M1)*：任何任何wT(M),如果如果w=,因为因为(T(M1)0，而而(T(M1)0(T(M1)*，所以所以(T(M1)*,所以所以w(T(M1)*。如果如果w，根据根据M的结构可以看出，一定可以将的结构可以看出，一定可以将w写写成成w=w1w2w3wk形式，形式，其中其中k1，每个每个wi(1ik)都使得在都使得在M1中从中从q1出发沿着标有出发沿着标有wi的路径达到的路径达到f1,识别识别完完wk后最后经过后最后经过转移达到状态转移达到状态f0，M接受输入接受输入w。显然上述每个显然上述每个wi(1ik)都属于都属于T(M1),所以所以w1w2w3wk(T(M1)k,(T(M1)k(T(M1)*，所以所以w1w2w3wk(T(M1)*，所以所以w(T(M1)*。于是得于是得T(M)(T(M1)*类似可以证明类似可以证明(T(M1)*T(M)。最后得最后得T(M)=(T(M1)*。【例【例2-4.1】给定正规表达式给定正规表达式r=01*1，构造一个构造一个-NFAM,使得使得T(M)=L(r)。解解.1.先将先将r分解，找出分解，找出r中所含基本符号中所含基本符号0、1、1，然后分别构造出接受这些基本符号的有限自动机，如下然后分别构造出接受这些基本符号的有限自动机，如下图所示图所示。q5q61q1q20q3q41q3q41q7q8q1q20q3q41q7q82.按照运算的优先权，从高到低进行按照运算的优先权，从高到低进行“组装组装”。先组装接受先组装接受1*的有限自动机，如下：的有限自动机，如下：再组装接受再组装接受01*的有限自动机，如下的有限自动机，如下：最后组装接受最后组装接受01*+1的有限自动机的有限自动机M，如下：如下：fq0q3q41q7q8q1q20q5q61此此NFAM就是接受正规表达式就是接受正规表达式r的有限自动机。的有限自动机。上面我们讨论了由给定的正规表达式上面我们讨论了由给定的正规表达式r求接受求接受r的有限自的有限自动机，当然可以将动机，当然可以将NFAM等价转换成等价转换成NFA,进而还可进而还可以转换成以转换成DFA。下面的问题就是，给定下面的问题就是，给定DFAM，如何求出如何求出T(M)的正规的正规表达式的问题。表达式的问题。定理定理2-4.2如果语言如果语言L可由一个可由一个DFAM接受，则接受，则L可用可用一个正规表达式表示。一个正规表达式表示。证明证明：设：设L由一个由一个DFAM(K,q1,F)接受，不妨接受，不妨设设K=q1,q2,qn。求求T(M)所对应的正规表达式所对应的正规表达式r，即使即使得得L(r)=T(M)。因为因为T(M)T(M)是由是由上这样字符串上这样字符串w w构成的集合，这些字符构成的集合，这些字符串串w w都使得都使得M M从开始状态从开始状态q q1 1出发沿着标有出发沿着标有w w的路径，途中经的路径，途中经过过K K中某些状态，而最后达到中某些状态，而最后达到F F中的某个状态。为此我们中的某个状态。为此我们定义符号串集合定义符号串集合 。：是由：是由上这样字符串上这样字符串x x构成的集合，这些构成的集合，这些x x都使得都使得M M从状态从状态q qi i出发沿着标有出发沿着标有x x的路径，最后到达的路径，最后到达q qj j,而途中经而途中经过所有状态的下标都不大于过所有状态的下标都不大于k k。就表示使得就表示使得M M从状态从状态q qi i出发，最后到达出发，最后到达q qj j的所有符号的所有符号串构成的集合。于是串构成的集合。于是问题是如何计算问题是如何计算，下面就给出它的递归计算公式，下面就给出它的递归计算公式：其其中中表表示示从从状状态态qi出出发发，不不经经过过任任何何状状态态直直接接到到达达qj的的所所有有符符号号串串构构成成的的集集合合。因因此此当当ij时时，就就是是M的的有有向向图图上上从从qi到到qj的的有有向向边边上上标标的的符符号号构构成成的的集集合合。当当i=j时时，除除了有向环上标的符号外，还包括了有向环上标的符号外，还包括。由两部分组成：由两部分组成：一部分是一部分是，中的符号串中的符号串x可使得可使得M从状态从状态qi出发出发沿着标有沿着标有x的路径，最后到达的路径，最后到达qj,而途中经过所有状态的而途中经过所有状态的下标都不大于下标都不大于k-1,而不经过状态而不经过状态qk。qjqkqix1kxkkxkj另一部分是另一部分是，其中的符号串，其中的符号串x可使得可使得M从状从状态态qi出发沿着标有出发沿着标有x的路径，最后到达的路径，最后到达qj,而途中必经过而途中必经过状态状态qk。这里这里x可以由三个子串的连接组成，例如，可以由三个子串的连接组成，例如，xik,xkk,xkj,则则x=xik(xkk)*xkj，识别识别x的路的路线如下图所示：线如下图所示：显然显然可以用正规表达式可以用正规表达式表示，它的计算公式如下：表示，它的计算公式如下：下下面面通通过过一一个个例例子子说说明明如如何何应应用用上上面面公公式式求求DFAM的的T(M)的正规表达式的正规表达式r.【例【例2-4.1】给定给定DFAM如如图图2-4.2所示。求所示。求T(M)的正规的正规表达式表达式r.解解1.k=0q20,1q1q31 10 01 10 0图图2-4.22.K=1:3.K=24.K=35.T(M)的正规表达式的正规表达式r为为：作业题作业题1化简正规表达式化简正规表达式a(+aa)*(+a)b+b+(ab*+b)*2构构造造一一个个FAM，使使得得T(M)的的正正规规表表达达式为式为01+(0+1)*1)*。3给给定定FAM如如下下图图所所示示，求求它它所所接接收收的的语言语言T(M)的正规表达式。的正规表达式。q2q100112-5 有限自动机的简化 对于给定的一个有限自动机对于给定的一个有限自动机M，有时可以在保证接受语有时可以在保证接受语言言T(M)不变的情况下，进行简化，即求一个含有更少状不变的情况下，进行简化，即求一个含有更少状态的有限自动机态的有限自动机M，使得使得T(M)=T(M)。例如下面有限自动机例如下面有限自动机M就可以简化成就可以简化成M，它们接受的语它们接受的语言都是言都是1*,如图如图2-5.1所示。所示。图图2-5.1q21 1q31 11 1q11 11 1M:q11 1M:给定一个给定一个DFAM,如何进行简化。主要的思路是先定义如何进行简化。主要的思路是先定义自动机状态集合自动机状态集合K上的一个等价关系上的一个等价关系，然后用，然后用 将将K进进行划分得到商集行划分得到商集K/，再构造状态更少的有限自动机。再构造状态更少的有限自动机。一一.定义定义K上等价关系上等价关系 给定给定DFAM=(K,q0,F)，p,qK,p q对对 x*,有有(p,x)F(q,x)F如果如果p q也称也称p与与q是不可区分的。是不可区分的。二二.商集商集K/【例例2-5.1】给定给定DFAM(K,q0,F)，K=a,b,c,d,e,f,=0,1,F=c,d,e，M的的如图如图2-5.2所示，显然所示，显然T(M)的的正规表达式为正规表达式为0*10*。为了求商集为了求商集K/,需要对所有需要对所有x*,进行考察进行考察,才能判断哪才能判断哪些状态之间有等价关系些状态之间有等价关系，进而得到商集，进而得到商集K/,但是由于但是由于*是无限集合，这里是无限集合，这里*=,0,1,00,01,10,11,000,001,010,abcf0,100111001de01图图2-5.2无法考察无法考察*中的每个中的每个x,为方便，将为方便，将*分成三个子集：分成三个子集：Ax|x*且且x中无中无1Bx|x*且且x中只有一个中只有一个1Cx|x*且且x中至少有两个中至少有两个1*ABC,A,B,C是是*的一个划分。的一个划分。a FF Fb FF FcF F FdF F FeF F Ff F F Fx Ax Bx Cxq(q,x)(q,x)abcf0,100111001de01图图2-5.2ab,cd,ce,de,ff,于是得商集：于是得商集：K/a,b,c,d,e,f从此例子看出，由于一般来说从此例子看出，由于一般来说*是无限集合，所以按照是无限集合，所以按照 的的定定义义判判断断哪哪些些状状态态之之间间有有等等价价关关系系，是是个个很很难难的的事事情情，甚至无法实现。甚至无法实现。下面我们下面我们换一种思维换一种思维，是否可以判断哪些状态之间无等，是否可以判断哪些状态之间无等价关系价关系，即考虑，即考虑 的逆关系的逆关系，从而求得商集。，从而求得商集。三三 的逆关系的逆关系 对于任何对于任何p,qK，p q x(x*(p,x)F(q,x)F),对于此式对于此式两边同时取否定两边同时取否定得：得：p q x(x*(p,x)F(q,x)F)x(x*(p,x)F(q,x)F)(p,x)F(q,x)F)x(x*，使得使得(p,x)与与(q,x)恰有一个在恰有一个在F中中)如果如果p q,称称p与与q是可区分的是可区分的。判断。判断p q是比较容易的。是比较容易的。4 4判断可区分状态对的算法判断可区分状态对的算法引理引理2-1设设M=(K,q0,F)是是DFA，则状态对则状态对(p,q)是可区分是可区分的的(即即p q)，当且仅当在下面算法中当且仅当在下面算法中(p,q)格写上格写上。begin1forpF,qK-F,do给给(p,q)格写格写；2forFF或或(K-F)(K-F)中每个状态对中每个状态对(p,q)(pq)，do3if a，使得格使得格(p,a),(q,a)内已经写上内已经写上，thenbegin4给给(p,q)格写格写；5如果刚刚写上如果刚刚写上的格内有先前写入的状态对，此状态对的格内有先前写入的状态对，此状态对的格同时也写入的格同时也写入。反复执行。反复执行5,直到写入直到写入的格内没的格内没有先前写入的状态对为止；有先前写入的状态对为止；endelse/*格格(p,a),(q,a)内无内无*/6for每个每个a,do7把把(p,q)写入格写入格(p,a),(q,a)内，除非内，除非(p,a)=(q,a)。end为了了解此算法的思想，我们先看一看对例为了了解此算法的思想，我们先看一看对例2-6应用此应用此算法的结果，再证明此引理。算法的结果，再证明此引理。执行此算法的结果用一个表表示，实际上，执行此算执行此算法的结果用一个表表示，实际上，执行此算法的过程就是向这个表内写入法的过程就是向这个表内写入“”“”的过程。的过程。a b c d ebcdef (a,b)abcf0,100111001de01图图2-5.2最后得最后得a b，c d，c e，d e，f f，于是于是K/a,b,c,d,e,f，这与前面得到的结果是一致的这与前面得到的结果是一致的。下面就是对例下面就是对例2-5.1执行此算法的过程：执行此算法的过程：1因为因为a,b,fK-F,c,d,eF,所以下面格写所以下面格写：(a,c),(a,d),(a,e),(b,c),(b,d),(b,e),(f,c),(f,d),(f,e)。因为这些状态对可以用因为这些状态对可以用区分。区分。2下面考察下面考察FF或或(K-F)(K-F)中状态对中状态对(p,q)(其中其中pq)：考察考察(a,b)：因因(a,0)=b，(b,0)=a，这说明这说明a与与b用用0是区分不开的，是区分不开的，又又(a,1)=c，(b,1)=d，因因(c,d)格内无格内无，说明说明a与与b是否可区分，是否可区分，取决于取决于c与与d，所以根据算法的第所以根据算法的第7步，步，将将(a,b)写入写入(c,d)格内。格内。abcf0,100111001de01图图2-5.2考察考察(a,f):因为因为(a,0)=b,(f,0)=f，而而(b,f)格无格无；再看再看(a,1)=c，(f,1)=f，而而(c,f)格内已写格内已写，所以根，所以根据据算法的第算法的第3,4步步,(a,f)格也写入格也写入。考察考察(b,f)：(b,0)=a(f,0)=f，而而(a,f)格内已写格内已写，根据算法的第根据算法的第3，4步，步，(b,f)格写入格写入。考察考察(c,d)：(c,0)=e(d,0)=e，(c,1)=f,(d,1)=f，可见可见(c,d)不可区分，故不可区分，故c d。abcf0,100111001de01图图2-5.2考察考察(c,e)：(c,0)=e(e,0)=e，(c,1)=f,(e,1)=f，可见可见(c,e)不可区分，故不可区分，故c e。考察考察(d,e)：(d,0)=e(e,0)=e，(d,1)=f(e,1)=f，可见可见(d,e)不可区分，故不可区分，故d e。此外，由于此外，由于(c,d)不可区分，不可区分，所以所以(a,b)也是不可区分的，也是不可区分的，故有故有a b。最后得最后得a b，c d，c e，d e，f f，于是于是K/a,b,c,d,e,f，这与前面得到的结果是一致的。这与前面得到的结果是一致的。abcf0,100111001de01图图2-5.2a b c d ebcdef (a,b)引理引理证明证明：必要性必要性，(设设(p,q)可区分，证出可区分，证出(p,q)格格内必写入内必写入。)充分性充分性，(设设(p,q)格写入格写入，通过对表中，通过对表中的个数归纳证明的个数归纳证明(p,q)一定可一定可区分。区分。)证明过程从略。证明过程从略。五构造简化的有限自动机五构造简化的有限自动机定理定理2-5.1给定给定DFAM(K,q0,F)，可根据引理可根据引理2-1中中的算法构造出除去不可达状态的具有更少状态的的算法构造出除去不可达状态的具有更少状态的DFAM，使得使得T(M)=T(M)。证明：证明：先对先对M用引理用引理2-1中的算法求出中的算法求出K/。再构造再构造M：M=(K,q0,F)，其中其中K=q|qK/且在且在M中中q是从是从q0可达的状态可达的状态F=q|qF：对任何对任何qK，任何任何a,(q,a)=(q,a)下面我们还是先针对例下面我们还是先针对例2-5.1中的中的M，按照此定理的方法，按照此定理的方法，求求M。应用引理应用引理2-1后已经求得后已经求得K/=a,b,c,d,e,f=a,c,f，其中其中a=a,b，c=c,d,e，f=f。K=a,c,f，q0=a，F=cM=(a,c,f,0,1,a,c)(a,0)=(a,0)=b=a(a,1)=(a,1)=c(c,0)=(c,0)=e=c(c,1)=(c,1)=f(f,0)=(f,0)=f(f,1)=(f,1)=fM的图，如图的图，如图2-5.2所示。所示。显然，显然，M接受的语言也是接受的语言也是0*10*。图图2-5.2Mc1 10,10,10 00 01 1faabcf0,100111001de01图图2-5.2M定理的证明定理的证明简要说明：简要说明：首先，证明首先，证明定义的一致性。定义的一致性。即即对对任任何何p,qK，如如果果p q，即即p=q,则则对对任任何何a，必有必有(p,a)(q,a),进而有进而有(p,a)=(q,a)。这样说明，一个等价类中，任哪一个元素作为此等价类这样说明，一个等价类中，任哪一个元素作为此等价类的代表元素是无关紧要的。的代表元素是无关紧要的。其次，用对其次，用对|w|归纳证明：对任何归纳证明：对任何w*，有有(q0,w)=(q0,w)。最后，证明最后，