计算理论课件第二章.ppt

第二章第二章 有限自动机和正规文法有限自动机和正规文法2.1 确定的有限自动机确定的有限自动机( (DFA)DFA) (Determinate Finite Automaton )    有限自动机是研究自动系统的一种数学模型，它出现有限自动机是研究自动系统的一种数学模型，它出现于本世纪四十年代于本世纪四十年代1943年由年由McCulloch与与Pitts建立了模拟神经网络的自动机建立了模拟神经网络的自动机,1956年由年由Moore建立了描述计算机的时序机的概念建立了描述计算机的时序机的概念以后自动机的理论日趋发展，并且与计算机的信息处理以后自动机的理论日趋发展，并且与计算机的信息处理密切结合，它不仅用于研究计算机的结构，还用于研究密切结合，它不仅用于研究计算机的结构，还用于研究形式语言形式语言——语言的识别语言的识别   在这里主要是从识别语言这方面来研究自动机在这里主要是从识别语言这方面来研究自动机一一.有限自动机有限自动机(FA)的结构的结构   有限自动机由三部分构成：有限自动机由三部分构成：1.输入带输入带  输入带可以任意长，带上输入带可以任意长，带上有若干单元，每个单元内有若干单元，每个单元内有输入符号。

输入带上存有输入符号输入带上存放的是被有限自动机识别放的是被有限自动机识别的符号串如图所示，的符号串如图所示，   输入带上的符号串为：输入带上的符号串为：     a1 a2 a3  …… an2.读头读头     读头是将输入带上的符号读到有限控制器中，每次读读头是将输入带上的符号读到有限控制器中，每次读一个单元的符号一个单元的符号 有有 限限 控控 制制 器器a1   a2  a3   … … an输入带输入带读头读头3.有限控制器有限控制器 有限控制器是有限自动机的核心有限控制器是有限自动机的核心 有限自动机有多个状态，有一个开始状态，还有限自动机有多个状态，有一个开始状态，还有若干个终止状态有若干个终止状态 自动机每读带上一个符号自动机每读带上一个符号, ,状态可能发生变化，状态可能发生变化，然后读头右移一个单元然后读头右移一个单元 自动机如何从开始状态出发，识别完带上的整自动机如何从开始状态出发，识别完带上的整个符号串后，要进入某个终止状态，这个过程就个符号串后，要进入某个终止状态，这个过程就是由有限控制器控制的是由有限控制器控制的。

二二.确定的有限自动机确定的有限自动机(DFA)的形式描述的形式描述定义定义：确定的有限自动机：确定的有限自动机M写成有序五元组，记写成有序五元组，记作作M=(K,∑,δ, q0 ,F) 其中，其中，    K——有限自动机的状态的有限集合有限自动机的状态的有限集合   ∑——输入带上的有穷字母表输入带上的有穷字母表      δ——状态转移函数状态转移函数,是是 K×∑→K 的映射   例如，例如，δ(q,a)= p (其中其中q,p∈∈K , a∈∈∑ ), 表示在表示在q状态下，读状态下，读a后，状态改为后，状态改为p ,然后，将读头右移然后，将读头右移一个单元一个单元  q0 ——开始状态开始状态 q0∈∈K            F———— 终止状态集合，终止状态集合， 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 1q0   q2   q1q1   q3    q0q2   q0   q3q3    q1   q2aqδ(q,a)=q     (c)  F   (d) q q0 0   开始状态开始状态q0          (a)q q p pδ(q,a)= p        (b)a有限自动机还可以有限自动机还可以用图表示用图表示方法如下：方法如下：四．状态转移函数四．状态转移函数δ定义的扩充定义的扩充        原原δ：： K×∑→K 的映射          1100q0q1q2q311000 10 1q0   q2   q1q1   q3    q0q2   q0   q3q3    q1   q2        (q,ε)=q        M 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 其中其中p∈∈F}例例2-1.1中，中，T(M)=?  1100q0q1q2q31100T(M)={w|w∈∈{0,1}*且且w中有偶数个中有偶数个0或者偶数个或者偶数个1}。

•作业题作业题1．．设设计计一一个个有有限限自自动动机机(FA)  M，，使使得得T(M)中中的的每每个个句句子子w同同时时满满足足下下面面三三个个条件：条件：    1) w∈∈{a,b,}*；；    2) |w|是是3的整数倍；的整数倍；    3) w以以a开头，以开头，以b结尾2．．设计二个设计二个FA M1和和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。

    δ—状态转移函数状态转移函数,  是是 K×∑→2K 的映射 例例. .δ(q,a)={p,s} (δ(q,a)={p,s} (其中其中q∈K,{p,s}∈q∈K,{p,s}∈2K a∈∑ ) a∈∑ ) 【例【例2-2.1】】 .给定给定NFA M，， M=(K,∑,δ,q0 ,F)其中，其中，K={q0,q1,q2,q3,q4} ∑={0,1}  F={q2,q4}   δ：：K×∑→2K 为：为：           0         1q0  {q0,q3}  {q0,q1}q1   Φ         {q2}q2    {q2}       {q2}q3    {q4}          Φ      q4    {q4}      {q4}q0q1q2q3q40,10,10,10011图图2-2.1 NFA MNFA M状态转移图状态转移图二二.状态转移函数状态转移函数δ定义的扩充定义的扩充    原来原来δ：：K×∑→2K，，下面对它进行下面对它进行两次扩充两次扩充与确   定的有穷自动机相类似，定的有穷自动机相类似，扩充以后的状态转移函数仍扩充以后的状态转移函数仍   然用然用δ。

因为这样做因为这样做, 在计算时也不会引起错误在计算时也不会引起错误1. 将将δ扩充成：扩充成：δ：：K×∑*→2K，，定义为：定义为：  x∈∈∑*,    δ(q,x)={p1,p2,…,pn}（（{p1,p2,…,pn}∈∈2K ））   表示在状态表示在状态q下下,读读符号串符号串x后后,可以达到状态可以达到状态pi (1≤i≤n)  一般地表示：一般地表示：    δ(q,ε)={q}    q∈∈K           δ(q,xa)                               其中其中q∈∈K , x∈∈∑*，，a∈∈∑δ(q0,01)=δ(q0,1)∪∪δ(q3,1)={q0,q1}∪∪Φ={q0,q1}例例2-2.1中中  δ(q0,0)={q0,q3},  则则   为了计算为了计算δ(q,xa)方便，方便，2. 将将δ的定义再一次扩充成：的定义再一次扩充成：δ：：2K×∑→2K，，   对于任何对于任何P＝＝{p1,p2,…,pn}∈∈2K，，a∈∈∑           (2)  δ(q,xa) =δ(δ(q,x),a)即即δ(P,a)等于等于P中每个状态分别读中每个状态分别读a后状态集合的并集。

后状态集合的并集δ的定义经过扩充之后，计算的定义经过扩充之后，计算δ(q,xa)的式子可写成：的式子可写成：    δ(q,xa)=δ(δ(q,x),a)    于是对于任何于是对于任何x∈∈∑*,a∈∑    (1) δ(q,ε)={q}    q∈∈Kδ(P,a)=δ({p1,p2,…,pn},a)=三三.  NFA M所接收的语言所接收的语言T(M)    给定给定NFA  M=(K,∑,δ,q0,F), M所接收的语言所接收的语言T(M)为：为：    T(M)={w|w∈∈∑*且且δ(q0 ,w)∩F≠Φ}    例例2-2.1中，中，T(M)=?T(M)={w|w∈∈{0,1}*且且w中或者有两个相邻的中或者有两个相邻的0或者有两或者有两           个相邻的个相邻的1}q0q1q2q3q40,10,10,10011图图2-2.1 NFA MNFA M状态转移图状态转移图四．四．NFA转换成转换成DFA    任何一个任何一个NFA都可以等价地转换成都可以等价地转换成DFA   定理定理2-2.1 如果语言如果语言L可由一个可由一个NFA M所接收，则必存所接收，则必存在一个在一个DFA M’，，使得使得T(M’)=L。

   证明证明：令：令NFA M=(K,∑,δ,q0 ,F)，，且且T(M)=L构造构造DFA M’=(K’,∑, δ’, q0’,F’), 其中其中   K’ 2K，，K’中的元素是由中的元素是由K的子集的子集{q1,q2,…,qi}构成，但构成，但是要把子集是要把子集{q1,q2,…,qi}作为的一个状态看待，因此把此作为的一个状态看待，因此把此子集写成子集写成[q1,q2,…,qi] q0’=[q0] ,  F’={[q1,q2,…,qi]|[q1,q2,……,qi]∈∈K’且且{q1,q2,…,qi}∩F≠Φ}δ’ ：：K’×∑→K’，，对对 [q1,q2,…,qi]∈∈K’,   a∈∈∑，，有有      δ’([q1,q2,…,qi],a)=[p1,p2,…,pj]当且仅当当且仅当      δ({q1,q2,…,qi},a)={p1,p2,…,pj}    这说明：计算这说明：计算δ’时，完全取决于时，完全取决于NFA中中δ（（注注：为了更好地理解如何根据：为了更好地理解如何根据NFA M构造构造DFA M’’，，可可以先看例子，然后再看下面的证明，这样更容易理解证以先看例子，然后再看下面的证明，这样更容易理解证明的过程。

明的过程 例例. 将例将例2-2.12-2.1中的中的NFA MNFA M等价变换成等价变换成DFA M’DFA M’按照上述按照上述定定理给定的方法令理给定的方法令M’M’＝＝(K’,∑,δ’, q0’,F’)，，     其中，其中，K’、、F’:    因因为为K’ 2K，，在在求求K’时时，，不不需需要要将将2K中中的的所所有有元元素素都都列列入入K’,只需要列入只需要列入从开始状态从开始状态[q0]可以达到的状态即可可以达到的状态即可,为为此可以先求此可以先求δ’ ，然后得到，然后得到K’和和F’例例2-2.1：：NFA  M=(K,∑,δ,q0 ,F)  其中，其中，K={q0,q1,q2,q3,q4}             ∑={0,1}        F={q2,q4}  构造构造DFA M’=(K’,∑, δ’, q0’,F’),     q0’ =[q0]    δ’ :   [q1,q2,…,qi]∈∈K’,  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,q3}∪∪{q4}                        ={q0,q3,q4},   于是于是    δ’([q0,q3],0)=[q0,q3,q4],其余的依此类推其余的依此类推 最后得下表最后得下表          0         1q0  {q0,q3}  {q0,q1}q1   Φ         {q2}q2    {q2}       {q2}q3    {q4}          Φ      q4    {q4}      {q4}δ:    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  [q0]    [q0,q3]           [q0,q1]            [q0,q3]    [q0,q3,q4]       [q0,q1]             [q0,q1]    [q0,q3]            [q0,q1,q2]        [q0,q3,q4]   [q0,q3,q4]        [q0,q1,q4]        [q0,q1,q2]   [q0,q2,q3]        [q0,q1,q2]        [q0,q2,q3]   [q0,q2,q3,q4]    [q0,q1,q2]        [q0,q1,q4]   [q0,q3,q4]        [q0,q1,q2,q4]    [q0,q2,q3,q4]   [q0,q2,q3,q4]   [q0,q1,q2,q4]    [q0,q1,q2,q4]   [q0,q2,q3,q4]   [q0,q1,q2,q4] ]δ’：：          0         1q0  {q0,q3}  {q0,q1}q1   Φ         {q2}q2    {q2}       {q2}q3    {q4}          Φ      q4    {q4}      {q4}δ: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.2 M’的状态转移图的状态转移图[ [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∈∈∑*, 如果如果x∈∈T(M’)，，则则δ’(q0’’,x)∈∈F’，，令令 δ’(q0’’,x)=[p1,p2,…,pj]，，即即[p1,p2,…,pj] ∈∈F’     因命题因命题 δ’(q0’’,x)=[p1,p2,…,pj]  当且仅当当且仅当 δ(q0,x)={p1,p2,…,pj} 成立。

成立    由由F’定义得定义得 [p1,p2,…,pj]∈∈F’ 当且仅当当且仅当     {p1,p2,…,pj}∩F≠Φ，，即即δ(q0,x)∩F≠Φ   于是于是x∈∈T(M)   所以所以T(M’)=T(M) 定理证明完毕定理证明完毕   从从此此定定理理看看出出:与与DFA相相比比，，NFA并并没没有有扩扩大大它它所所接接收收语言的范围语言的范围作业题作业题给定给定NFA M1 =({p,q,r,s},{0,1},δ,p,{s})，，如下如下表所示构造一个表所示构造一个DFA M2，，使得使得T(M1)=T(M2) δ     0       1  p  {p,q}  {p}     q   {r }   {r}    r   {s}     Φ    s   {s}     {s}2.3   具有具有εε转移的转移的NFA （（简记成简记成ε-ε-NFA））       前边讨论的前边讨论的NFA中的输入符号只是中的输入符号只是∑中的符号，在理中的符号，在理论上和实际应用中还有另一种论上和实际应用中还有另一种NFA，，就是输入符号中除就是输入符号中除了了∑中的符号以外，还允许有中的符号以外，还允许有ε，，这就是具有这就是具有ε转移的转移的NFA(ε-NFA)。

例【例2-3.1】】具有具有ε转移的转移的NFA M(ε-NFA M)，，如图如图2-3.1所示从图中看出，所示从图中看出，图中有的有向边上标有图中有的有向边上标有εq0q1q2012εε图图2-3.1ε-NFA Mε-NFA M图图一．一．ε-NFA的形式定义的形式定义ε-NFA M=(K,∑,δ,q0 ,F)，，其中其中K,∑,q0 ,F的含义同前边的含义同前边NFA, δ: K×(∑∪∪{ε})→2K     例例2-3.1中的中的ε-NFA M 的的δ如表如表2-3.1所示 0     1     2    εq0    {q0}  Φ    Φ  {q1}q1     Φ   {q1}  Φ  {q2}q2     Φ    Φ   {q2} Φ表表2-3.12-3.1ε-NFA Mε-NFA M状态转移表状态转移表q0q1q2012εε图图2-3.1ε-NFA Mε-NFA M图图为了讨论为了讨论ε-NFA 接收的语言需要对接收的语言需要对δ的定义进行扩充的定义进行扩充二．二．δ的定义扩充的定义扩充       先扩充成先扩充成     ：：K×∑*→2K,定义为定义为,对于对于 q∈∈K, w∈∈∑*,    值得注意值得注意: :在在DFADFA和和NFANFA中中, ,对于扩充后的对于扩充后的 与与δδ可以不加可以不加(q0,ε)={q0}径径(即在即在0的前后可能有若干个的前后可能有若干个ε)，，而不是输入符号而不是输入符号0。

    (q0,0)={q0,q1,q2}≠δ(q0,0)={q0}, 因为这里的因为这里的0指的是指的是0路路  (q0,ε)={q0,q1,q2}≠δ(q0,ε)= {q0} ，，因为这里的因为这里的ε指的是指的是ε路径，而不是边上标的路径，而不是边上标的ε而在而在ε-NFA中，在例中，在例2-3.1中中   (q0,0)={q0,q3}=δ(q0,0)区别的使用，因为它们的计算结果相同但是在这里区别的使用，因为它们的计算结果相同但是在这里就就必须加以区别必须加以区别, ,因为它们的计算结果不同了请看下例因为它们的计算结果不同了请看下例: :在在NFA中，在例中，在例2-2.1中，中，     (q,w)=P={p| 从从q出发，沿着标有出发，沿着标有w的的路径路径达到状态达到状态p}q0q1q2012εε图图2-3.1ε-NFA Mε-NFA M图图为了写出为了写出     (q,w)的计算公式，下面再定义两个概念的计算公式，下面再定义两个概念三．三．ε-CLOSURE(q)     q∈∈K,ε-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}五五.对对δ及的定义的再扩充及的定义的再扩充    将将δ的定义扩充成的定义扩充成δ：：2K×∑→2K，，   注意注意,     (q,wa)≠δ(    (q,w),a)，，因路径因路径wa,是指是指wε*aε*,    (q,wa)=ε-CLOSURE(δ(     (q,w),a))公式公式(2)：： 对于对于 q∈∈K,  w∈∈∑*,  a∈∈∑,公式公式(1)：对于：对于 q∈∈K, ,       (q,ε)=ε-CLOSURE(q)六．的计算公式六．的计算公式对对 R∈∈2K,  w∈∈∑*,         (R,w)=            (r,w)再扩充成再扩充成     ：：2K×∑*→2K,     (δ(    (q,w),a))前边加前边加ε-CLOSURE。

所以要在所以要在对对 R∈∈2K，，  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}七七.ε-NFA M接收的语言接收的语言T(M)   给定一个给定一个ε-NFA M=(K,∑,δ,q0 ,F)，，它接收的它接收的语言语言T(M)为：为： T(M)={w|w∈∈∑*且且     (q0,w)∩F≠Φ}上例中上例中   T(M)={0i1j2k|i,j,k≥0}八八.ε-NFA等价地转换为等价地转换为NFA    一个一个ε-NFA M可以等价地转换为没有可以等价地转换为没有ε转移转移的的NFA。

下面介绍定理下面介绍定理定理定理2-3.1 如果语言如果语言L由一个有由一个有ε转移的转移的NFA M所接收，则所接收，则L可被一个不具有可被一个不具有ε转移的转移的NFA M’所接收证明：证明：令一个令一个ε-NFA M=(K,∑,δ,q0 ,F)，，它接收的语言它接收的语言T(M)为为L构造一个不具有构造一个不具有ε转移的转移的NFA M’ M’=(K, ∑, δ’,q0 ,F’)，，其中其中       δ’ ：对任何：对任何q∈∈K,任何任何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)  (根据的扩充定义根据的扩充定义)=    (      (q0,x),a)   (根据假设（根据假设（2））)=      (q0,xa)综上所述，上述命题成立综上所述，上述命题成立先证先证T(M) T(M’)    任取任取x∈∈T(M)，，若若x＝＝ε，，则则ε-CLOSURE(q0)∩F ≠Φ，，由由F’的构成得的构成得F’=F∪∪{q0}，，而而δ’ (q0,ε)＝＝{q0},所以所以δ’(q0,ε)∩F’≠Φ，，所以所以ε∈∈T(M’)   若若x≠ε，，则则    (q0,x)∩F≠Φ，，由已经证明的命题得由已经证明的命题得 δ’(q0,x)∩F≠Φ，，由由F’定义得定义得F F’，，所以所以 δ’(q0,x)∩F’≠Φ，，所以所以 x∈∈T(M’)     所以所以T(M) T(M’)。

 再证再证T(M’)  T(M)     任取任取x∈∈T(M’),下面分两种情况下面分两种情况  1) 如果如果x=ε，，因因M’是无是无ε的的NFA，，必有必有     δ’(q0,ε)={q0} F’ ，，所以所以q0∈∈F’，，再分两种情况讨论再分两种情况讨论:  (1) 若若q0∈∈F，，又有又有q0∈∈ε-CLOSURE(q0),  所以所以   ε-CLOSURE(q0)∩F≠Φ, 而而即即    (q0,ε)∩F≠Φ，，所以所以ε∈∈T(M) (2) 若若q0 F ，，而而q0∈F’∈F’，，这说明这说明F’F’=F∪∪{q0}，，即说即说明明ε-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≠Φ，，所以所以x∈∈T(M)。

(2) 如如果果F’=F∪∪{q0}，，又又已已知知δ’(q0,x)∩F’≠Φ，，这这又又有有两两种种可能：可能：   (a)  若若q0  δ’(q0,x)，，则有则有       δ’(q0,x)∩F’＝＝δ’(q0,x)∩(F∪∪{q0})             ＝＝ δ’((q0,x)∩F)∪∪(δ’(q0,x)∩{q0})             ＝＝ (δ’(q0,x)∩F)∪∪Φ             ＝＝ δ’(q0,x)∩F  ≠Φ 即即    (q0,x)∩F≠Φ，，所以所以x∈∈T(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’=F∪∪{q0}，，由由F’定义知定义知 ε-CLOSURE(q0)∩F≠Φ，，于是于是  δ’(q0,x)∩F≠Φ，，所以所以  δ’(q0,x)∩F’≠Φ，，所以所以x∈∈T(M)。

综上所述，有综上所述，有T(M’) T(M)最后得最后得T(M’)=T(M)例例.下面将例下面将例2-3.1中的中的ε-NFA M等价变换成等价变换成NFA M’令令M’=(K,∑, δ’, q0,F’)，，其中其中K={q0,q1,q2},∑={0,1,2},F’={q0,q2}, δ’的计算如下：的计算如下：图图2-3.2 NFA M’图图q0q2q10,1,22100,11,2 0 1 20 1 2  q0  {q0,q1,q2}  {q1,q2}  {q2} q1     Φ          {q1,q2}   {q2 2} } q2     Φ             Φ       {q2}δ’:δ’(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.2M’的图如图的图如图2-3.2所示作业题作业题  将下面的将下面的ε-NFA M等价变换成等价变换成NFA M’abcdefε1εεε0102.4 正规表达式及其与有限自动机之间正规表达式及其与有限自动机之间的等价性的等价性    有限自动机所接受的语言，很容易用字母表上的符号有限自动机所接受的语言，很容易用字母表上的符号串以及符号串上的一些运算符号构成的表达式来表示，串以及符号串上的一些运算符号构成的表达式来表示，即用正规表达式来表示即用正规表达式来表示一一.正规表达式定义正规表达式定义设设Σ是有限字母表，是有限字母表，Σ上的正规表达式及其所代表的符上的正规表达式及其所代表的符号串集合递归定义如下：号串集合递归定义如下：  1.φ是个正规表达式，它代表空集是个正规表达式，它代表空集Φ  2.ε是个正规表达式，它代表集合是个正规表达式，它代表集合{ε}  3. 任何任何a∈∈Σ，，是个正规表达式，它代表集合是个正规表达式，它代表集合{a}  4.如果如果r、、s分别是代表集合分别是代表集合R、、S的正规表达式的正规表达式,则则(r+s)、、  (rs)、、(r*)分别是代表集合分别是代表集合(R∪∪S)、、(RS)、、(R*)的正规表的正规表达式。

达式   r+s称作称作r与与s的加运算；的加运算； rs 称作称作r与与s的连接运算；的连接运算；   r* 称作称作r的的*闭包运算闭包运算  设设r是个正规表达式，则是个正规表达式，则r所代表的集合记作所代表的集合记作L(r)  例如例如 ，，L(ε)={ε},   L(a)={a}二．正规表达式运算的优先级二．正规表达式运算的优先级   为了书写简单，看起来也简单明了，我们规定了正规为了书写简单，看起来也简单明了，我们规定了正规表达式运算的优先权，于是正规表达式的最外层的括号表达式运算的优先权，于是正规表达式的最外层的括号以及表达式里的一些括号可以省略以及表达式里的一些括号可以省略   运算的优先权运算的优先权:从高到低依次是：从高到低依次是：*、连接、＋连接、＋   因此，因此，(0+(0(1*)))可以简记为可以简记为 0＋＋01*    例如例如 设设 Σ＝＝{0,1}，， 则则   1. 01 表示集合表示集合 L(01)＝＝{0}{1}={01}   2. 0+1 表示集合表示集合 L(0+1)= L(0)L(1)={0}∪∪{1}={0,1}   3. (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)*)={1}{0,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*＝＝A0∪∪A∪∪A2∪∪A3∪∪A4∪∪……  其中其中A0={ε},   所以所以L(φ*)＝＝Φ*=Φ0∪∪Φ∪∪Φ2∪∪……=Φ0={ε}=L(ε)  11. α+α*=α*  12. (α*)*=α*在离散数学中在离散数学中,二元关系二元关系R有，有， R*=rt(R)=tr(R), (  R*)*=R*  13. αα*=α*α=α+在离散数学中，二元关系在离散数学中，二元关系R有，有，(R◦R*)=R*◦R=R+  14. (ε+α) *=α*因因 L((ε+α)*)={ε,α}*={ε,α}0∪∪{ε,α}1∪∪{ε,α}2∪∪……={ε}∪∪{ε,α}∪∪{ε,α,α2 }∪∪{ε,α,α2 ,α3}∪∪…={ε,α,α2 α 3,……}={α}*=L(α*)  15. ε+α+=α*   16. (αα) *+α*=α*因为因为{αα}* {α}*五五.正规表达式与有限自动机之间的等价性正规表达式与有限自动机之间的等价性   下面证明有限自动机所接受的语言正好是一个正规表下面证明有限自动机所接受的语言正好是一个正规表达式所表示的语言。

反之亦然达式所表示的语言反之亦然,即任意给定正规表达式即任意给定正规表达式r,都可以确定一个都可以确定一个FA M，，使得使得T(M)=L(r)正规表达式与有限自动机之间的等价关系，可以用下面正规表达式与有限自动机之间的等价关系，可以用下面图图2-4.1表示正规表达式正规表达式εε－－NFANFADFA图图2-4.1 有限自动机与正规表达式之间的等价转换关系图有限自动机与正规表达式之间的等价转换关系图定理定理2-4.1 设设r是是Σ上的一个正规表达式，则存在一个具上的一个正规表达式，则存在一个具有有ε转移的转移的NFA M, 使得使得T(M)=L(r)证明证明：用对：用对r中含有运算的个数归纳证明中含有运算的个数归纳证明1.如如果果r中中有有0个个运运算算，，则则有有三三种种可可能能: r=φ,r=ε,r=a a∈∈Σ,则则有下面三个自动机分别接受它们有下面三个自动机分别接受它们q0q0q1aq0q1r=φr=φr=εr=εr=ar=a2.假设假设r中运算个数少于中运算个数少于k个时，结论成立个时，结论成立3.当当r中有中有k个运算时，因正规表达式中只有三种运算，所个运算时，因正规表达式中只有三种运算，所以分三种情况讨论：以分三种情况讨论：(1) 如果如果r=r1+r2, 则则r1和和r2中运算个数少于中运算个数少于k个，由假设得，个，由假设得，  存在存在ε－－NFA M1和和M2 ，， 使得使得    T(M1)=L(r1)    T(M2)=L(r2),不妨设不妨设M1＝＝(K1 ,Σ1 ,δ1 , q1 ,{f1})   M2＝＝(K2 ,Σ2 ,δ2,q2,{f2}) 设设 K1∩K2=Φ 下面构造下面构造ε－－NFA M  M＝＝(K1∪∪K2∪∪{q0,f0} ,Σ1∪∪Σ2 ,δ,q0,{f0})，， 其中其中q0 ,f0   K1 ∪∪K2 ,使得使得T(M)=T(M1)∪∪T(M2)=L(r1)∪∪L(r2)=L(r1+r2), 于是于是M的结构如下图所示：的结构如下图所示： M1M2q1q2q0f1f2f0εεεεεεεεM的状态转移函数的状态转移函数δ为：为：①① δ(q0,ε)={q1,q2}       M可以进入可以进入M1和和M2的开始状态。

的开始状态②② 对任何对任何q∈∈K1 , 任何任何a∈∈Σ1∪∪{ε} 有有    δ(q,a)=δ1(q,a)         M可以模拟可以模拟M1的动作③③ 对任何对任何q∈∈K2 , 任何任何a∈∈Σ2∪∪{ε} 有有   δ(q,a)=δ2(q,a)       M可以模拟可以模拟M2的动作④④δ(f1,ε)=δ(f2,ε)={f0}很容易证明很容易证明T(M)=T(M1)∪∪T(M2)，，这里从略这里从略(2).如果如果 r=r1r2 , 则则 r1和和r2中运算个数少于中运算个数少于k个个,由假设得，由假设得，存在存在ε－－NFA M1和和M2 使得使得T(M1)=L(r1) T(M2)=L(r2), M1和和M2如前所述如前所述下面构造下面构造ε－－NFA M＝＝(K1∪∪K2,Σ1∪∪Σ2 ,δ,q1,{f2})，，使使得得T(M)=T(M1)T(M2)=L(r1)L(r2)=L(r1r2), 于是于是M的结构如的结构如下图所示：下图所示：   M1q1f1M2q2εεf2M的状态转移函数的状态转移函数δ为：为：①①  对任何对任何q∈∈K1 , 任何任何a∈∈Σ1∪∪{ε} 有有     δ(q,a)=δ1(q,a)     M可以模拟可以模拟M1的动作。

的动作②② δ(f1 ,ε)={q2}③③ 对任何对任何q∈∈K2 , 任何任何a∈∈Σ2∪∪{ε} 有有     δ(q,a)=δ2(q,a)     M可以模拟可以模拟M2的动作很容易证明很容易证明T(M)=T(M1)T(M2)，，这里从略这里从略(3).如果如果 r=r1*, 则则 r1中运算个数少于中运算个数少于k个，由假设得，存个，由假设得，存在在ε－－NFA M1 使得使得T(M1)=L(r1) ,M1 如前所述如前所述下面构造下面构造ε－－NFA M＝＝(K1∪∪{q0,f0},Σ1 ,δ,q0,{f0})，，使得使得T(M)=(T(M1))*=(L(r1))* =L(r1*), 于是于是M的结构如下的结构如下图所示：图所示：    q0M1q1f1f0εεεεεεεεM的状态转移函数的状态转移函数δ为：为：①① δ(q0,ε)={q1,f0}   ②② 对任何对任何q∈∈K1 , 任何任何a∈∈Σ1∪∪{ε} 有有    δ(q,a)=δ1(q,a)     M可以模拟可以模拟M1的动作③③δ(f1,ε)={q1,f0}下面证明下面证明T(M)=(T(M1))*：：   任何任何w∈∈T(M),    如果如果w=ε,因为因为ε∈∈(T(M1))0，，而而 (T(M1))0 (T(M1))*，，所以所以ε∈∈(T(M1))* , 所以所以w∈∈(T(M1))*。

    如果如果w≠ε，，根据根据M的结构可以看出，一定可以将的结构可以看出，一定可以将w写写成成 w =w1w2w3…wk形式，形式， 其中其中k≥1，，每个每个wi (1≤i≤k)都使得在都使得在M1中从中从q1出发沿着标有出发沿着标有wi的路径达到的路径达到f1 ,识别识别完完wk后最后经过后最后经过ε转移达到状态转移达到状态f0 ，，M接受输入接受输入w  显然上述每个显然上述每个wi(1≤i≤k)都属于都属于T(M1),所以所以w1w2w3…wk∈∈(T(M1))k, (T(M1))k (T(M1))*，，所以所以w1w2w3…wk∈∈(T(M1))* ，， 所以所以w∈∈(T(M1))*于是得于是得 T(M) (T(M1))*类似可以证明类似可以证明(T(M1))* T(M)最后得最后得T(M)=(T(M1))*【例【例2-4.1】】 给定正规表达式给定正规表达式r=01*＋＋1，，构造一个构造一个ε-NFA M, 使得使得T(M)=L(r)解解. 1. 先将先将r 分解，找出分解，找出r中所含基本符号中所含基本符号——0、、1、、1，，然后分别构造出接受这些基本符号的有限自动机，如下然后分别构造出接受这些基本符号的有限自动机，如下图所示图所示。

q5q61q1q20q3q41q3q41q7q8εεεεεεεεq1q20εεq3q41q7q8εεεεεεεε2. 按照运算的优先权，从高到低进行按照运算的优先权，从高到低进行“组装组装”①①先组装接受先组装接受1*的有限自动机，如下：的有限自动机，如下：②②再组装接受再组装接受01*的有限自动机，如下的有限自动机，如下：③③最后组装接受最后组装接受01*+1的有限自动机的有限自动机M，，如下：如下：fq0εεq3q41q7q8εεεεεεεεq1q20εεq5q61εεεεεε     此此ε－－NFA M就是接受正规表达式就是接受正规表达式r的有限自动机的有限自动机    上面我们讨论了由给定的正规表达式上面我们讨论了由给定的正规表达式r求接受求接受r的有限自的有限自动机，当然可以将动机，当然可以将ε－－NFA M等价转换成等价转换成NFA, 进而还可进而还可以转换成以转换成DFA    下面的问题就是，给定下面的问题就是，给定DFA M，，如何求出如何求出T(M)的正规的正规表达式的问题表达式的问题     定理定理2-4.2 如果语言如果语言L可由一个可由一个DFA M接受，则接受，则L可用可用一个正规表达式表示。

一个正规表达式表示    证明证明：设：设L由一个由一个DFA M＝＝(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的的所所有有符符号号串串构构成成的的集集合合因因此此当当i≠j时时，，就就是是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的路的路  线如下图所示：线如下图所示：显然显然    可以用正规表达式可以用正规表达式    表示，它的计算公式如下：表示，它的计算公式如下：下下面面通通过过一一个个例例子子说说明明如如何何应应用用上上面面公公式式求求DFA M的的T(M)的正规表达式的正规表达式r.【例【例2-4.1】】 给定给定DFA M如如图图2-4.2所示求T(M)的正规的正规表达式表达式r.解解 1. k=0q20,1q1q31 10 01 10 0图图2-4.22. K=1:3.K=24.K=35. T(M)的正规表达式的正规表达式r为为： •作业题作业题1．．化简正规表达式化简正规表达式  a(ε+aa)*(ε+a)b+b+φ(ab*+b)*2．．构构造造一一个个FA M，，使使得得T(M)的的正正规规表表达达式为式为01+((0+1)*1)*3．．给给定定FA M如如下下图图所所示示，，求求它它所所接接收收的的语言语言T(M)的正规表达式。

的正规表达式q2q100112-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’:给定一个给定一个DFA M ,如何进行简化主要的思路是先定义如何进行简化主要的思路是先定义自动机状态集合自动机状态集合K上的一个等价关系上的一个等价关系  ，然后用，然后用 将将K进进行划分得到商集行划分得到商集K/  ，，再构造状态更少的有限自动机再构造状态更少的有限自动机一一.定义定义K上等价关系上等价关系    给定给定DFA M=(K,∑,δ,q0,F)，，    p,q∈∈K,    p q  对对  x∈∈∑*, 有有              δ(p,x)∈∈Fδ(q,x)∈∈F  如果如果p q 也称也称p与与q是不可区分的。

是不可区分的二二.商集商集K/ 【【例例2-5.1】】 给定给定DFA M＝＝(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,   为方便，将为方便，将∑*分成三个子集：分成三个子集：  A＝＝{x| x∈∈∑*且且x中无中无1}  B＝＝{x| x∈∈∑*且且x中只有一个中只有一个1}  C＝＝{x| x∈∈∑*且且x中至少有两个中至少有两个1} ∑*＝＝A∪∪B∪∪C, {A,B,C}是是∑*的一个划分的一个划分a          F       ∈∈F       Fb          F       ∈∈F       Fc         ∈∈F        F       Fd         ∈∈F        F       Fe         ∈∈F        F      Ff           F        F        Fx Ax Bx Cxqδ(q,x)δ(q,x)abcf0,100111001de01图图2-5.2ab, cd,ce,de, ff,于是得商集：于是得商集：K/{{a,b},{c,d,e},{f}}    从此例子看出，由于一般来说从此例子看出，由于一般来说∑*是无限集合，所以按照是无限集合，所以按照 的的定定义义判判断断哪哪些些状状态态之之间间有有等等价价关关系系 ，，是是个个很很难难的的事事情情，，甚至无法实现。

甚至无法实现   下面我们下面我们换一种思维换一种思维，是否可以判断哪些状态之间无等，是否可以判断哪些状态之间无等价关系价关系 ，即考虑，即考虑 的逆关系的逆关系 ̷̷，从而求得商集从而求得商集三．三． 的逆关系的逆关系 ̷̷    对于任何对于任何p,q∈∈K，，   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)格写上格写上×。

begin 1．．for p∈∈F,q∈∈K-F, do 给给(p,q)格写格写×；；2．．for F×F或或(K-F)×(K-F)中每个状态对中每个状态对(p,q) (p≠q)，，do3．．if  a∈∈∑，，使得格使得格(δ(p,a),δ(q,a))内已经写上内已经写上×，，then       begin4．．    给给(p,q)格写格写×；；5．．   如果刚刚写上如果刚刚写上×的格内有先前写入的状态对，此状态对的格内有先前写入的状态对，此状态对         的格同时也写入的格同时也写入×反复执行反复执行5, 直到写入直到写入×的格内没的格内没         有先前写入的状态对为止；有先前写入的状态对为止；       end    else /**  格格(δ(p,a),δ(q,a))内无内无×  **/6．．for 每个每个a∈∈∑, do 7．．把把(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,f∈∈K-F, c,d,e∈∈F,所以下面格写所以下面格写×：：   (a,c) ,(a,d), (a,e), (b,c), (b,d) ,(b,e) ,(f,c), (f,d) ,(f,e)   因为这些状态对可以用因为这些状态对可以用ε区分2．．下面考察下面考察F×F或或(K-F)×(K-F)中状态对中状态对(p,q)     (其中其中p≠q)：： 考察考察(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 dabcf0,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 给定给定DFA M＝＝(K,∑,δ,q0,F)，，可根据引理可根据引理2-1中中的算法构造出除去不可达状态的具有更少状态的的算法构造出除去不可达状态的具有更少状态的DFA M’，，使得使得T(M’)=T(M)。

证明：证明：先对先对M用引理用引理2-1中的算法求出中的算法求出K/ 再构造再构造M’：：M’=(K’,∑,δ’,[q0], F’)，，其中其中   K’={[q]| [q]∈∈K/ 且在且在M中中q是从是从q0 可达的状态可达的状态}   F’={[q]| q∈∈F}  δ’：：对任何对任何[q]∈∈K’，，任何任何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’={[c]}M’=({[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)]=[f]M’的图，如图的图，如图2-5.2所示。

所示显然，显然，M’接受的语言也是接受的语言也是0*10*图图2-5.2  M’[c]1 10,10,10 00 01 1[f][a]abcf0,100111001de01图图2-5.2 M定理的证明定理的证明——简要说明：简要说明：首先，证明首先，证明δ’定义的一致性定义的一致性    即即对对任任何何p,q∈∈K，，如如果果p q，，即即[p]=[q],则则对对任任何何a∈∈∑，，必有必有δ(p,a) δ(q,a), 进而有进而有[δ(p,a)]=[δ(q,a)] 这样说明，一个等价类中，任哪一个元素作为此等价类这样说明，一个等价类中，任哪一个元素作为此等价类的代表元素是无关紧要的的代表元素是无关紧要的 其次，用对其次，用对|w|归纳证明：对任何归纳证明：对任何 w∈∑∈∑*，，有有           δδ’([q0],w)=[δδ(q0,w)] 最后，证明最后，证明T(M’)=T(M)作业题作业题将下面有限自动机简化将下面有限自动机简化(要求有简化过程要求有简化过程)abcfed00,10 001011112.6 正规集对运算的封闭性正规集对运算的封闭性     所谓所谓正规集正规集，就是有限自动机所接收的语言，或者是，就是有限自动机所接收的语言，或者是正规表达式表示的语言，或者是正规文法产生的语言正规表达式表示的语言，或者是正规文法产生的语言(后后面要介绍正规文法与有限自动机之间的等价性面要介绍正规文法与有限自动机之间的等价性)。

    这一节将介绍正规集对并、交、补、乘积、这一节将介绍正规集对并、交、补、乘积、*闭包及逆闭包及逆转运算的封闭性转运算的封闭性定理定理2-6.1 正规集对并、乘积、正规集对并、乘积、* 闭包运算是封闭的即闭包运算是封闭的即 设设L1和和L2都是正规集都是正规集,则则L1∪∪L2、、L1L2及及L1*也是正规集也是正规集证明：证明：用正规表达式证明令用正规表达式证明令r1、、r2,分别是表示分别是表示L1、、L2的的正规表达式则正规表达式则r1＋＋r2、、r1r2 及及r1*分别是表示分别是表示L1∪∪L2、、L1L2及及L1*的正规表达式所以的正规表达式所以L1∪∪L2、、L1L2及及L1*也是正也是正规集定理定理2-6.2 正规集对补运算封闭正规集对补运算封闭即设即设L是正规集，且是正规集，且L ∑1*，，又又∑1 ∑2，，∑1与与∑2都是字都是字母表，则母表，则∑2*－－L也是正规集也是正规集分析：分析：为了便于理解证明过程，先用一个例子为了便于理解证明过程，先用一个例子说明证明思想说明证明思想假设有一个有限自动机假设有一个有限自动机M＝＝(K,∑1,δ,q0,F)，，且且T(M)=L，，∑1 ∑2，，• L中的所有符号串都使得中的所有符号串都使得M  从从q0出发最后达到出发最后达到F中的某中的某  个状态而被个状态而被M接收。

接收•∑1*－－L中的所有符号串都使得中的所有符号串都使得M从从q0出发最后达到出发最后达到K－－F中的某个状态，或中的某个状态，或者无可达状态，而不被者无可达状态，而不被M接收 如图如图2-6.1所示 ∑∑1*L∑∑2*∑∑2*-∑-∑1*∑∑1*- -L L图图2-6.1   构造构造M’，，使得使得   T(M’)=∑2*—L为此让为此让M’如此工作如此工作：：1. M的终止状态集合的终止状态集合F中的状态中的状态   成为成为M’的非终止状态，的非终止状态，   从而不接收从而不接收L中的符号串中的符号串2. M’的终止状态集合的终止状态集合  F’=(K－－F) {d}    终止状态终止状态d称之为收容状态，称之为收容状态，3. ∑1*—L中的所有符号串中的所有符号串  使使M’从开始状态从从开始状态从q0出发出发  最后达到最后达到K－－F 中的状态，或者中的状态，或者d状态而被状态而被M’接收接收  ∑∑1*L∑∑2*∑∑2*-∑-∑1*∑∑1*- -L L图图2-6.2 M’进入F(K－－F) {d}进入{d}*.这样就使得这样就使得M能接收的符号能接收的符号  串串M’都不接收，而都不接收，而M不不接接  收符号串可被收符号串可被M’接收。

接收4.而而∑2*—∑1*中的所有符号串都使中的所有符号串都使M’从开始状态从从开始状态从q0出出  发最后达到发最后达到d状态而被状态而被M’接收例如，例如，给定接收给定接收0*10*的有限自动机的有限自动机M（（∑1={0,1}））如图如图2-6.3所示，所示，T(M)=L，，∑2={0,1,2},求一个有限自动机求一个有限自动机M’，，使得使得T(M’)=∑2*—L按照上面思路构造按照上面思路构造M’如图如图2-6.4所示图图2-6.3  Mq11 10 00 0q0图图2-6.4  M’1 1q00 02 20,1,20,1,20 0q11,21,2d下面继续证明定理下面继续证明定理证明证明：令：令DFA M＝＝(K,∑1,δ,q0,F)，，且且T(M)=L,∑1 ∑2，，d K现在构造一个有限自动机现在构造一个有限自动机M’, 使得使得T(M’)=∑2*-L，，令令M’=(K∪∪{d},∑2,δ’,q0,(K-F)∪∪{d}),δ’定义如下：定义如下：1．．对任何对任何q∈∈K，，任何任何a∈∈∑1，，如果如果δ(q,a)有定义，则有定义，则     δ’(q,a)＝＝δ(q,a)；；2．．对任何对任何q∈∈K，，任何任何a∈∈∑1，，如果如果δ(q,a)无有定义，则无有定义，则    δ’(q,a)＝＝d；；3．．对任何对任何q∈∈K，，任何任何a∈∈∑2－－∑1，，有有δ’(q,a)＝＝d；；4．．对任何对任何a∈∈∑2，，有有δ’(d,a)＝＝d。

于是任何于是任何w∈∈T(M’)，，当且仅当当且仅当δ’(q0,w)∈∈(K-F)∪∪{d}因此因此δ(q0,w) F，，即即w T(M)，，所以所以w∈∈∑2*—L所以所以T(M’)=∑2*—L    当当∑2＝＝∑1 时，时，∑1*—L＝＝     所以如果所以如果L是正规集，是正规集，则则L的补集也是正规集即正规集对补运算是封闭的的补集也是正规集即正规集对补运算是封闭的定理定理2-6.3 正规集对交运算封闭如果正规集对交运算封闭如果L1和和L2都是正规集，都是正规集，则则L1∩L2也是正规集也是正规集证明证明：设：设L1和和L2都是正规集，因为都是正规集，因为L1∩L2＝＝              , 且根据正规集对并、补运算封闭，所以且根据正规集对并、补运算封闭，所以L1∩L2也是正规也是正规集   下面介绍下面介绍语言的语言的“逆转逆转”运算运算R：：   L是一个语言，则是一个语言，则L的逆转记作的逆转记作LR   LR＝＝{wR|w∈∈L}   wR是符号串是符号串w的逆转，的逆转，   例如例如w=0100，，则则wR=(0100)R=0010 设设L是正规集，则是正规集，则L的逆转的逆转LR也是正规集。

也是正规集分析：举例分析：举例说明证明的思路说明证明的思路 给定有限自动机给定有限自动机M如图如图2-6.5所示，它所接收的语言所示，它所接收的语言      T(M)=L的正规表达式是的正规表达式是10*，，图图2-6.5  Mq11 10 0q0图图2-6.6 M’q01 10 0q1M’的构造方法是的构造方法是：将：将M的开始状态变成终止状态，将终的开始状态变成终止状态，将终止状态变成开始状态（因为止状态变成开始状态（因为M只有一个终止状态），再只有一个终止状态），再将所有有向边的方向颠倒即可（环的方向不必改变）将所有有向边的方向颠倒即可（环的方向不必改变）LR是是0*1，接收的有限自动机为，接收的有限自动机为M’如图如图2-6.6所示如果如果M有两个终止状态，如何处理？有两个终止状态，如何处理？若如果若如果M有多个终止状态，可以增加一个新的开始状态，有多个终止状态，可以增加一个新的开始状态，构造构造M’如图如图2-6.7所示所示定理定理2-6.4 正规集在正规集在“逆转逆转”运算下是封闭的运算下是封闭的证明证明：令：令DFA M＝＝(K,∑,δ,q0,F)，，且且T(M)=L，，L是正规是正规集。

构造接收集构造接收LR的的ε-NFA M’，，M’=(K∪∪{q0’},∑1,δ’,q0’,{q0})，，δ’构造如下：构造如下：(1) δ’(q0’,ε)=F；；(2) 对任何对任何q∈∈K，，任何任何a∈∈∑，，如果如果δ(q,a)=p，，则则q∈∈δ’(p,a)即将即将M的有向图中有向边的方向颠倒的有向图中有向边的方向颠倒)很容易证明很容易证明T(M’)=(T(M))R =LR 1 1q21 1q00 00 0M:q1图图2-6.71 11 1q00 00 0M’:q1q2q0'εεεε2.7 正规文法与有限自动机之间的正规文法与有限自动机之间的等价性等价性通过证明正规文法与通过证明正规文法与有限自动机之间的相互转换来说明：有限自动机之间的相互转换来说明：正规文法所产生的语言，也是正规集正规文法所产生的语言，也是正规集 正规文法正规文法，它分成右线性和左线性两类它分成右线性和左线性两类  右线性：产生式形式为：右线性：产生式形式为：AxB, Cy  左线性：产生式形式为：左线性：产生式形式为：ABx, Cy,        A,B,C是非终极符，是非终极符，x,y是终极符串。

是终极符串例【例2-7.1】】  G1=({S,A},{0,1},P,S)：：S0A，，A10A，，Aε  G2=({S,A},{0,1},P,S)：：SA，，AA10，，A0G1就是右线性文法，就是右线性文法，G2是左线性文法容易看出它们产是左线性文法容易看出它们产生的语言是相同的，都是生的语言是相同的，都是0(10)*1.1.右线性和左线性相互转换右线性和左线性相互转换定理定理2-7.1 给定右线性文法给定右线性文法G，，当且仅当存在左线性文法当且仅当存在左线性文法G’，，使得使得L(G)=L(G’)证明：证明：设文法设文法G=(ＶＶＮＮ,ＶＶＴＴ,ＰＰ,S)是右线性文法，不妨设是右线性文法，不妨设ＶＶＮＮ＝＝{S,A1,A2,…,An}，，且且S不出现在不出现在P中产生式的右侧中产生式的右侧（如果出现，就引进新的开始变元（如果出现，就引进新的开始变元S0，，再增加产生式再增加产生式S0S）下面构造左线性文法下面构造左线性文法G’=(ＶＶＮＮ,ＶＶＴＴ,ＰＰ’,S)，，其中其中P’构成如下：对任何构成如下：对任何Ai,Aj∈∈ＶＶＮＮ，任何，任何α∈∈ＶＶＴＴ*,   (1) Sα,      当且仅当当且仅当    Sα∈∈P；；   (2) Aiα,     当且仅当当且仅当    SαAi∈∈P；；   (3) AiAjα,   当且仅当当且仅当    AjαAi∈∈P；；   (4) SAjα,    当且仅当当且仅当    Ajα∈∈P。

下面证明下面证明L(G’)=L(G)先证明先证明L(G’) L(G)，，任取任取w∈∈L(G’), 则则G’有派生有派生S*w，，下面分两种情况讨论：下面分两种情况讨论：a) 如果此派生是一步完成的，即如果此派生是一步完成的，即Sw，，则有则有Sw∈∈P’，，由由P’构成可知构成可知Sw∈∈P，，所以在所以在G中也有派生中也有派生Sw，，所所以以w∈∈L(G)b) 如果此派生是多于一步完成的，不妨设此派生为：如果此派生是多于一步完成的，不妨设此派生为：SAi1α1 Ai2α2α1Ai3α3α2α1… Aim-1αm-1αm-2…α2α1 αmαm-1…α2α1=w，，则说明则说明P’中有产生式：中有产生式：SAi1α1，，Ai1Ai2α2，，Ai2Ai3α3，，…，，Aim-2Aim-1αm-1，，Aim-1αm 由由P’构成可知在构成可知在P中有相应产生式：中有相应产生式：Ai1α1，，Ai 2 α2Ai1，，Ai3α3Ai2 ，，…，，Aim-1αm-1Aim-2，，Sαm Aim-1 于是于是G中有派生：中有派生：SαmAim－－1αmαm－－1Aim－－2 … αmαm－－1…α2Ai1 αmαm－－1…α2α1=w 。

所以所以w∈∈L(G)，，所以所以L(G’) L(G)     用类似的方法可以证明用类似的方法可以证明L(G) L(G’)，，    最后得最后得 L(G’)=L(G)    根据此定理，以后我们讲正规文法时，它是右线性文法根据此定理，以后我们讲正规文法时，它是右线性文法还是左线性文法是无关紧要的还是左线性文法是无关紧要的下面为了讨论正规文法与有限自动机之间的等价性，先介下面为了讨论正规文法与有限自动机之间的等价性，先介绍简单右线性文法绍简单右线性文法2 2．简单右线性文法．简单右线性文法    定义定义：设：设G是个右线性文法，如果它的所有产生式都是个右线性文法，如果它的所有产生式都具有如下形式：具有如下形式：AaB, Cb, Dε, 其中其中A,B,C,D是变是变元，元，a,b是终极符，则称是终极符，则称G是个简单右线性文法是个简单右线性文法     任何一个右线性文法，都可以很容易地等价变换为简任何一个右线性文法，都可以很容易地等价变换为简单右线性文法单右线性文法   例如例如，上面文法，上面文法G1：：S0A, A10A, Aε，，其中其中    A10A，，可以变换为：可以变换为：A1B, B0A。

   最后得到与之等价的简单右线性文法最后得到与之等价的简单右线性文法: G1’=({S,A,B},{0,1},P’,S)，，其中其中P’为：为：         S0A, A1B, B0A, Aε，，3．．根据正规文法，求与之等价的有限自动机根据正规文法，求与之等价的有限自动机定理定理2-7.2设设G是个正规文法，则可以构造有限自动机是个正规文法，则可以构造有限自动机M，，使之使之T(M)=L(G)证明证明：假设：假设G已经是已经是简单的右线性简单的右线性文法，否则，要先将文法，否则，要先将G等价变换为简单的右线性文法，等价变换为简单的右线性文法，  令令G＝＝(ＶＶＮＮ,ＶＶＴＴ,ＰＰ,S)，，设设E ＶＶＮＮ   构造一个构造一个ε-NFA M=(K,∑,δ,q0,F)，，  其中其中K=ＶＶＮＮ∪∪{E}，，∑=ＶＶＴＴ，，q0=S，，F={E}，，即即  M=(ＶＶＮＮ∪∪{E},ＶＶＴＴ,δ,S,{E})，，其中其中δ构成如下：构成如下：  对任何对任何A,B,C∈∈ＶＶＮＮ，任何，任何a,b∈∈ＶＶＴＴ，则，则        （（1））B∈∈δ(A,a)   当且仅当当且仅当  AaB∈∈P    （（2））E∈∈δ(B,b)   当且仅当当且仅当  Bb∈∈P    （（3））E∈∈δ(C,ε)  当且仅当当且仅当  Cε∈∈P例如，对于上面给定的简单右线性文法例如，对于上面给定的简单右线性文法G1’：：       S0A, A1B, B0A, Aε，，按照此方法，构成与按照此方法，构成与G1’等价的有限自动机等价的有限自动机M如如图图2-7.1所示。

可见所示可见M接收的语言也是接收的语言也是0(10)*下面继续证明下面继续证明T(M)=L(G)证明证明T(M) L(G)，，任取任取w∈∈T(M)，，下面分两种情况讨论：下面分两种情况讨论：a).如果如果|w|≤1，，则则w＝＝a（（a∈∈∑，，即即a∈∈ＶＶＴＴ）或者）或者w＝＝ε，，这说明这说明E∈∈δ(S,a)或者或者E∈∈δ(S,ε)，，由由δ的构成可知的构成可知 Sa∈∈P或者或者Sε∈∈P，，于是有于是有a∈∈L(G),ε∈∈L(G)，，即即w∈∈L(G)0 0E1 1ABS0 0εε图图2-7.1  Mb).如果如果|w|≥2，，令令w＝＝a1a2…an ，，ai∈∈ＶＶＴＴ∪∪{ε} (i=1,2,…,n)，，不妨设不妨设M在识别在识别w时的路径如图时的路径如图2-7.2所示于是于是G中有产生式：中有产生式：Sa1A1，，A1a2A2 ,..., An-1an，，所所以以G中有派生：中有派生：Sa1A1a1a2A2… a1a2…an-1Ana1a2…an-1an=w，，所所以，以，w∈∈L(G)所以有所以有T(M) L(G)。

类似可以证明类似可以证明L(G) T(M)，，最后可得最后可得T(M)=L(G)S SA A1A A2A An…a2a3a1an其中其中, An=E图图2-7.24 4．．根据有限自动机，求与之等价的正规文法根据有限自动机，求与之等价的正规文法定理定理2-7.3 给定确定有限自动机给定确定有限自动机M=(K,∑,δ,q0,F)，，则存则存在正规文法在正规文法G，，使得使得L(G)=T(M)证明证明：：构造右线性文法构造右线性文法G＝＝(K,∑,P,q0)，，其中其中     P={qap|δ(q,a)=p}∪∪{qa|δ(q,a)∈∈F}显然有下面命题成立：显然有下面命题成立：   对任何对任何x∈∈ＶＶＴＴ*,δ(q,x)=p,当且仅当当且仅当 G中有派生中有派生 q*xp此命题的证明与定理此命题的证明与定理2-7.2证明证明b)的过程类似，这里从略的过程类似，这里从略)下面证明下面证明T(M)=L(G)先证先证T(M) L(G)，，任取任取w∈∈T(M)，，如果如果w=ε，，则说明有则说明有δ(q0,ε)∈∈F由由P的构成得的构成得P中有产中有产生式生式q0ε，，所以所以ε∈∈L(G)；；如果如果w≠ε，，不妨是不妨是w=xa且有且有  δ(q0,xa)＝＝δ(δ(q0,x),a)=δ(p,a)∈∈F，， 其中其中δ(q0,x)=p，，再根据前命题得再根据前命题得q0 * xp 。

 又由又由δ(p,a)∈∈F，， 得得P中有产生式中有产生式 pa，，于是于是G中有派生：中有派生：    q0xpxa=w，，所以所以w∈∈L(G)反之，类似可证反之，类似可证L(G) T(M)，，最后可得最后可得T(M)=L(G)由有限自动机由有限自动机M，，求一个与之等价的求一个与之等价的左线性文法左线性文法G时，有时，有两种方法：两种方法：1.可以先按照上述方法，先求一个与之等价的右线性文法可以先按照上述方法，先求一个与之等价的右线性文法后，再将此文法等价地转换为左线性文法后，再将此文法等价地转换为左线性文法2.另外一种方法，在介绍此方法之前，先介绍一个另外一种方法，在介绍此方法之前，先介绍一个文法文法“逆转逆转”的实例，然后再介绍有关定理的实例，然后再介绍有关定理例如例如，上面给定右线性文法，上面给定右线性文法G1＝＝({S,A},{0,1},P,S)，，     P：：S0A，，A10A，，Aε显然显然G1所产生的语言为：所产生的语言为：0(10)*构造文法构造文法G1’=({S,A},{0,1},P’,S)，，   P’：：SA0, AA01, Aε。

其中，其中，P’={AαR|Aα∈∈P，，其中其中αR是是α的逆转的逆转}显然显然G1’产生的语言是产生的语言是(01)*0，其刚好是，其刚好是0(10)*的逆转定定理理2-7.4 设设G＝＝(ＶＶＮＮ,ＶＶＴＴ,ＰＰ,S)是是右右线线性性文文法法，，则则构构造造一一个左线性文法个左线性文法G’＝＝(ＶＶＮＮ,ＶＶＴＴ,ＰＰ’,S)，，其中其中 P’={AαR|Aα∈∈P，，其中其中αR是是α的逆转的逆转}，，则则L(G’)=(L(G))R证明：证明：先用归纳法先用归纳法(对推导步数归纳对推导步数归纳)证明如下结论：对任证明如下结论：对任何何α∈∈(ＶＶＮＮ∪∪ＶＶＴＴ)*，在，在G中有派生中有派生S*α，，当且仅当当且仅当 在在G’中有派生中有派生 S*αR1））如果如果G中一步派生出中一步派生出α，，即有即有Sα，，则说明则说明Sα∈∈P，，根据根据P’的构成可知，当且仅当的构成可知，当且仅当 P’中有产生式中有产生式SαR ，，于是于是G’中有派生中有派生SαR，，结论成立结论成立2））假设假设G中有派生中有派生 S*α，，是少于是少于k步完成的，当且步完成的，当且仅当仅当 在在G’中有派生中有派生S*αR。

3））当当S*α1Bα1α2=α是由是由k步完成时，则步完成时，则S *α1B是由是由k-1步完成的，由假设（步完成的，由假设（2）得，当且仅当）得，当且仅当在在G’中有派生中有派生 S*(α1B)R=Bα1R，，又在第又在第k步派生步派生α1Bα1α2中，实际上是应用产生式中，实际上是应用产生式Bα2，，由由P’构构成得，当且仅当成得，当且仅当P’中有产生式中有产生式Bα2R，，于是于是G’中有派生：中有派生：  S*(α1B)R=Bα1Rα2Rα1R=(α1α2)R =(α)R所以结论成立所以结论成立于是有任何于是有任何w∈∈L(G)，，即即S * w，，当且仅当当且仅当 在在G’中有派中有派生生 S* wR，，wR∈∈L(G’)，，所以所以L(G’)=(L(G))R例例2-7.2】】给定给定DFA M如图如图2-7.3所示，分别求一个右线所示，分别求一个右线性文法和一个左线性文法使得产生的语言都是性文法和一个左线性文法使得产生的语言都是T(M)解解：先求右线性文法：先求右线性文法G，，令令G=({S,A,B,C,},{0,1},P,S),其中其中P：： S0A|1C|0|1       A1B|0C|0       B0A|1C|0|1       C0C|1C|0|1求左线性文法，有两种方法求左线性文法，有两种方法：：0 0C1 1BS0 00 0图图2-7.3  M:1 10,10,11 1A一种方法是一种方法是：根据右线性文法：根据右线性文法G求左线性文法求左线性文法G’：：按照定理按照定理2-7.1中给定的方法，得中给定的方法，得    由由P中中S0|1，，      得得P’中有中有S0|1；；    由由P中中S0A|1C，，得得P’中有中有A0,C1；；    由由P中中A1B|0C，，得得P’中有中有BA1, CA0；；    由由P中中A0，，        得得P’中有中有SA0；；    由由P中中B0A|1C，，得得P’中有中有AB0, CB1；；    由由P中中B0|1，，      得得P’中有中有SB0|B1；；    由由P中中C0C|1C，，得得P’中有中有CC0, CC1；；    由由P中中C0|1，，      得得P’中有中有SC0|C1。

最后得最后得P’：：SA0|B0|B1|C0|C1|0|1；；                   AB0|0；；                   BA1；；                   CA0|B1|C0|C1|1另一种方法是另一种方法是：分成如下三步完成分成如下三步完成a））先将先将M逆转成逆转成ε-NFA M’，，如图如图2-7.4所示显然所示显然T(M’)=(T(M))Rb））再根据再根据M’求一个与之等价求一个与之等价的右线性文法的右线性文法G：：G=({D,S,A,B,C},{0,1},P,D)其中其中P中生成式为：中生成式为：     DA|C     A0S|0B|0     B1A     C0A|1B|1S|1C|0C|1由于没有变元由于没有变元S的产生式，的产生式，所以其中的所以其中的A0S，，C1S可去掉0 01 1BA0 00 0图图2-7.4  M’1 10,10,11 1SDCεεεε0 0C1 1BS0 00 0图图2-7.3  M:1 10,10,11 1A最后得最后得P:     DA|C                     A0B|0                     B1A                     C0A|1B|1C|0C|1显然显然L(G)=T(M’)。

c））将右线性文法将右线性文法G逆转成左线性文法逆转成左线性文法G’，，使得使得L(G’)=(L((G))R令令G’=({D,S,A,B,C},{0,1},P’,D)其中其中P’为：为： DA|C                     AB0|0                     BA1                     CA0|B1|C1|C0|1显然显然L(G’)=(L((G))R=(T(M’))R=((T(M))R)R=T(M)作业题作业题1．．给定给定DFA M如图所示求一个左线性文法如图所示求一个左线性文法G，，使得使得L(G)=T(M)2．．首先构造一个右线性文法首先构造一个右线性文法G，，使得使得      L(G)={ai bj|i,j≥0}∪∪{ck|k≥0}再构造一个有限自动机再构造一个有限自动机M，，使得使得T(M)=L(G)3．．给定右线性文法给定右线性文法G=({S,B,C,D},{0,1}, P, S)，，其中其中P：：    S→B∣ ∣C，，             B→0B∣ ∣1B∣ ∣011 ,   C→0D∣ ∣1C∣ ∣ε,    D→0C∣ ∣1D试求一个试求一个FA M，，使得使得 T(M)=L(G)。

BAC10100,12.8 正规集的判定问题正规集的判定问题 这一节将讨论如下这一节将讨论如下四个判定问题四个判定问题：： ☆ ☆ 某个语言不是正规集；某个语言不是正规集； ☆ ☆ 给定的正规集是否为空集；给定的正规集是否为空集； ☆ ☆ 给定正规集不是空集时，那么它是有穷集合还是给定正规集不是空集时，那么它是有穷集合还是 无穷集合；无穷集合； ☆ ☆ 以及判定两个自动机是否等价以及判定两个自动机是否等价在判定这些问题时，都用到一个引理在判定这些问题时，都用到一个引理————正规集的泵作正规集的泵作用引理 下面先介绍这个引理下面先介绍这个引理1 1．正规集的泵作用．正规集的泵作用( (pumping) )引理引理给定一个确定的有限自动机给定一个确定的有限自动机M=(K,∑,δ,q0,F)，，设设|K|=n，，考虑一个输入符号串考虑一个输入符号串z∈∈∑*,|Z|≥n,不妨设不妨设z=a1a2…am-1am，，m≥n，，如果如果z∈∈T(M)，，设设M识别识别z的路径如图的路径如图2-8.1所示其中其中qm∈∈F)。

从此图看出，图中有从此图看出，图中有m+1状态，状态，m+1＞＞n，，而而M中只有中只有n个不同状态，这说明上面图中至少有两个状态相同，不个不同状态，这说明上面图中至少有两个状态相同，不妨设妨设qj=qk,(k≥j)，，于是上面图就变成如图于是上面图就变成如图2-8.2所示的图所示的图q0q1q2qm…a2a3a1am图图2-8.1此图可以简化如图此图可以简化如图2-8.3所示 可将可将z写成写成z=(a1a2a3…aj)(aj+1aj+ 2…ak-1ak)(ak+1ak+2… am)，，图图2-8.2q0q1q2qm…a2a3a1amqk-1qk+1qj(qk)…aj+2qj+1…ak+1aj+1ak-1akajak+2q0qmqj(qk)a1a2a3…ajaj+1aj+ 2…ak-1akak+1ak+ 2… am图图2-8.3因为因为z∈∈T(M)，，所以对任何整数所以对任何整数i≥0，，有有(a1a2a3…aj)(aj+1aj+ 2…ak-1ak)i(ak+1ak+2… am)∈∈T(M)如果设如果设u=a1a2a3…aj，，v=aj+1aj+ 2…ak-1ak，，W=ak+1ak+2… am,，，于是于是z=uvw，，|v|≥1，，且对任何整数且对任何整数i≥0，，有有uviw∈∈T(M)，，其中其中vi就是从就是从qj到到qk的循环的循环i次。

这次这就引出正规集的泵作用引理就引出正规集的泵作用引理引理引理2-8.1（正规集的泵作用引理）：设（正规集的泵作用引理）：设L是正规集，则必是正规集，则必存在一个常数存在一个常数n，，使得任何使得任何z∈∈L，，只要只要|z|≥n，，就可以将就可以将z写成写成z=uvw，，其中其中|uv|≤n，，|v|≥1，，且对任何整数且对任何整数i≥0，，有有uviw∈∈L证明证明：因为：因为L是个正规集，必存在有限自动机是个正规集，必存在有限自动机M，，使得使得T(M)=L，，设设 M=(K,∑,δ,q0,F)，，设设|K|=n，，对任何对任何z∈∈L，，只要只要|z|≥n，，如上面所述，就可以将如上面所述，就可以将z写成写成z=uvw，，其中其中|uv|≤n，，|v|≥1，，且对任何整数且对任何整数i≥0，，有有uviw∈∈L2 2．．判断某个语言不是正规集判断某个语言不是正规集【例【例2-8.1】】证明语言证明语言 L={       |i是自然数是自然数}不是正规集不是正规集证明：证明：(用反证法用反证法)（（1））假设假设L是个正规集是个正规集2））设设n是是L满足正规集泵作用引理常数。

满足正规集泵作用引理常数3））设设z＝＝         ，，|z|=n2>n，，显然显然z∈∈L，，于是根据正于是根据正规集的泵作用引理，可将规集的泵作用引理，可将z写成：写成：z=uvw，，其中其中|uv|≤n，，|v|≥1，，且对任何整数且对任何整数i≥0，，有有uviw∈∈L4））适当地选取适当地选取v和和i，，找矛盾从找矛盾从L的定义看出，只有的定义看出，只有0的个数是个完全平方数，才是的个数是个完全平方数，才是L中的句子所以就设法选中的句子所以就设法选取一个取一个i，，使得使得|uviw|不是完全平方数不是完全平方数   取取i=2，，因为因为n2＜＜|uv2w|≤n 2+n＜＜(n+1)2，，可见可见|uv2w|不不是完全平方数，所以是完全平方数，所以uv2w L，，这与泵作用引理矛盾所这与泵作用引理矛盾所以以L不是正规集不是正规集0i20n23 3．．正规集的有穷性判定正规集的有穷性判定定理定理2-8.1 具有具有n个状态的有限自动机个状态的有限自动机M接收的语言接收的语言T(M)：：（（1））是非空集，是非空集， 当且仅当当且仅当 M接收一个长度小于接收一个长度小于n的句子。

的句子2））是无穷集合，当且仅当是无穷集合，当且仅当 M接收一个长度大于或等于接收一个长度大于或等于n而小于而小于2n的句子证明证明：：（（1）充分性）充分性显然成立即如果显然成立即如果M接收一个长度小接收一个长度小于于n的句子，则的句子，则T(M)≠Φ下面证明下面证明必要性必要性：已知：已知T(M)≠Φ，，假设假设T(M)中没有一个中没有一个长度小于长度小于n的句子又令的句子又令z∈∈T(M),且且z是是T(M)中长度最短的中长度最短的句子假设句子假设x的长度不小于的长度不小于n，，即即|z|≥n，，根据正规集的泵根据正规集的泵作用引理得，可将作用引理得，可将z写成写成z=uvw，，其中其中|uv|≤n,，，|v|≥1，，且且对任何整数对任何整数i≥0，，有有uviw∈∈T(M)取取i=0，，得得uv0w＝＝uw∈∈L，，|uw|＜＜|z|，，这与这与z是是T(M)中长度最短的中长度最短的句子矛盾所以句子矛盾所以T(M)中必有一个长度小于中必有一个长度小于n的句子（（2））充分性，已知有充分性，已知有z∈∈T(M)，，且且n≤|z|＜＜2n根据正规根据正规集的泵作用引理，可将集的泵作用引理，可将z写成：写成：z=uvw，，其中其中|uv|≤n，，|v|≥1，，且对任何整数且对任何整数i≥0，，有有uviw∈∈T(M)。

因为因为i的取值的取值有无穷多个有无穷多个(i=1,2,3,4,…)，，因而，这样的句子有无穷多因而，这样的句子有无穷多个，个，所以所以T(M)是无限集合是无限集合必要性必要性，已知，已知T(M)是无限集合，假设是无限集合，假设T(M)中没有一个长中没有一个长度大于或等于度大于或等于n而小于而小于2n的句子因的句子因T(M)是无限集合，则是无限集合，则必存在必存在z∈∈T(M)，，且且|z|≥n，，令令z是长度大于是长度大于n的句子中长度的句子中长度最短的句子假设最短的句子假设|z|不小于不小于2n，，根据正规集泵作用引理得，根据正规集泵作用引理得，可将可将z写成写成z=uvw，，其中其中|uv|≤n，，|v|≥1，，且对任何整数且对任何整数i≥0有有uviw∈∈T(M)取取i=0，，得得uv0w＝＝uw∈∈T(M)，，则则a））要么要么n≤|uw|＜＜2nb））要么要么z 不是不是T(M)中长度大于中长度大于n的句子中最短的句子，产的句子中最短的句子，产生矛盾所以所以T(M)中必有一个长度大于或等于中必有一个长度大于或等于n而小于而小于2n的句子必要性成立必要性成立所以所以T(M)中必有一个长度大于或等于中必有一个长度大于或等于n而小于而小于2n的句子。

必要性成立必要性成立所以所以T(M)是无穷集合，当且仅当是无穷集合，当且仅当 M接收一个长接收一个长度大于或等于度大于或等于n而小于而小于2n的句子按照上面定理，可以说，存在算法用以判定具有按照上面定理，可以说，存在算法用以判定具有n个状态的有限自动机个状态的有限自动机M接收的语言接收的语言T(M)是否为是否为非空集、有穷集或者为无穷集合，非空集、有穷集或者为无穷集合，4 4．．判定两个自动机等价判定两个自动机等价定理定理2-8.2 存在算法，用以判定两个自动机是否等存在算法，用以判定两个自动机是否等价价(即它们接收的语言是否相等即它们接收的语言是否相等)证明证明：令有限自动机：令有限自动机M1与与M2接收语言分别是接收语言分别是L1和和L2根据正规集对交、并、补运算封闭得根据正规集对交、并、补运算封闭得,可可以由一个有限自动机以由一个有限自动机M接收即        T(M)= 而而T(M)=Φ，，当且仅当当且仅当 L1=L2根据定理根据定理2-8.1得得存在算法用以判定具有存在算法用以判定具有n个状态的有限自动机个状态的有限自动机M接收的语言接收的语言T(M)是否为非空集即存在算法用是否为非空集。

即存在算法用以判定是否有以判定是否有L1=L2•作业题•证明L＝{ai|i是个素数}不是正规集。