第4章正则语言的性质

1、1第第4章章 正则语言的性质正则语言的性质 2一、正则语言的封闭性质定义定义4.1 如果属于某一语言类的任何语言在某一特定运算下所如果属于某一语言类的任何语言在某一特定运算下所得的结果仍然是该类语言，则称该语言类对此运算是封闭的，得的结果仍然是该类语言，则称该语言类对此运算是封闭的，并称该语言类对此运算具有封闭性（并称该语言类对此运算具有封闭性（closure property）。）。 给定正则语言给定正则语言L1和和L2，它们的并集、交集、连接是否仍然是正，它们的并集、交集、连接是否仍然是正则语言？则语言？ 定理定理4.1 如果如果L1和和L2是正则语言，那么是正则语言，那么L1L2也是正则

2、语言。也是正则语言。证明：如果证明：如果L1和和L2是正则的，那么一定存在正则表达式是正则的，那么一定存在正则表达式r1和和r2，使得使得L1L（r1），），L2L（r2）。根据定义，）。根据定义，r1+r2是表示语言是表示语言L1L2的正则表达式。因此，正则语言对于并运算是封闭的。的正则表达式。因此，正则语言对于并运算是封闭的。3定理定理4.2 如果如果L是字母表是字母表 上的正则语言，则上的正则语言，则L= *-L是正则是正则语言。语言。证明：如果证明：如果L是正则的，设接受是正则的，设接受L的的DFA为为M（Q， ， ，q0，F）。）。下面构造下面构造DFA M：取取M与与M的终结状态集

3、互为补集，除了终结状态集为的终结状态集互为补集，除了终结状态集为Q-F外，外，M的其余结构都与的其余结构都与M相同，即相同，即 M(Q， ， ，q0，Q-F）显然，对于显然，对于M接受的串，接受的串，M将不接受，对于将不接受，对于M接受的串，接受的串，M将不接受。因此将不接受。因此L（M）= *-L 所以所以 *-L是正则语言。是正则语言。4例例1 设设DFA M如图所示如图所示q0Start011001q2q1 它接受的语言为它接受的语言为L=w01| w 0，1* ，即接受所有以，即接受所有以01结尾的结尾的0和和1组成的串，组成的串，用正则表达式的形式描述就是用正则表达式的形式描述就是L

4、（M）=（0+1）*01 *-L就是所有不以就是所有不以01结尾的由结尾的由0和和1组成的串。组成的串。右图给出了右图给出了 *-L （M）的自动机，的自动机，它把上图中的终结状态变为非它把上图中的终结状态变为非终结状态，非终结状态变为终终结状态，非终结状态变为终结状态。结状态。q2Start011001q1q05 定理定理4.3 如果如果L1和和L2是正则语言，则是正则语言，则L1L2是正则语言。是正则语言。证明：证明：用构造证明的方法：用构造证明的方法：设设L1L（M1），），L2L（M2），），其中其中DFA M1（Q1， ， 1，q0，F1），）， DFA M2（Q2， ， 2，p0，

5、F2），），构造构造DFA M=（Q1 Q2， ， ，F1 F2） ，其中其中：（：（Q1 Q2）Q1 Q2对对 p1 Q1，p2 Q2，a （，a）=，由定义可以看出，由定义可以看出，w被被M接受当且仅当接受当且仅当w同时被同时被M1和和M2接接受，因此，受，因此，L1L2是正则的。是正则的。6例例2 设有如图下的两个设有如图下的两个DFA，M1接受所有包含接受所有包含0的串，的串，M2接受所有包含接受所有包含1的串，的串，Startp01q0, 1a）Startr10s0, 1b）Startqspr1psqr10010, 10按定理4.3的构造方法，构造出的DFA M如右图所示,M接受的同

6、时含有0和1的串。7定理定理4.4 如果如果L1和和L2是正则语言，那么是正则语言，那么L1-L2也是正则语言。也是正则语言。证明：证明：根据集合差运算的定义有根据集合差运算的定义有 L1-L2= L1L2如果如果L1和和L2是正则的，根据定理是正则的，根据定理4.2，L2是正则的，是正则的，再由定理再由定理4.3，L1L2也是正则的。所以，正则语言在差运算也是正则的。所以，正则语言在差运算上是封闭的。上是封闭的。定理定理4.5 如果如果L1和和L2是正则语言，那么是正则语言，那么L1L2和和L1*也都是正则语也都是正则语言。言。证明：证明：如果如果L1和和L2是正则的，那么一定存在正则表达式

7、是正则的，那么一定存在正则表达式r1和和r2，使得，使得L1L（r1），），L2L（r2）。根据正则表达式的定义，）。根据正则表达式的定义，r1r2和和r1*分别是表示语言分别是表示语言L1L2和和L1*的正则表达式。因此，正则的正则表达式。因此，正则语言在连接和星闭包运算上都是封闭的。语言在连接和星闭包运算上都是封闭的。8定理定理4.6 如果如果L是正则语言，则是正则语言，则L的逆的逆LR= w| wT L（wT表示表示w的倒序）也是正则语言。的倒序）也是正则语言。 证明：证明：证法证法1（用构造自动机的方法）（用构造自动机的方法）假设假设L是正则语言，是正则语言， M是接受是接受L的自动机

8、，通过下面方法构的自动机，通过下面方法构造一个接受造一个接受LR的自动机的自动机M：（1）M中的弧是中的弧是M中所有弧的方向反转构成；中所有弧的方向反转构成；（2）M的终结状态是的终结状态是M的初始状态；的初始状态；（3）如果）如果M不止一个终结状态，则在不止一个终结状态，则在M中创建一个新的初中创建一个新的初始状态，从该状态出发到始状态，从该状态出发到M的所有终结状态都建立一个的所有终结状态都建立一个 转转移。移。修改后的修改后的NFA M接受接受wT，当且仅当，当且仅当M接受接受w。因此，。因此，M接接受受LR，从而证明了逆运算的封闭性。，从而证明了逆运算的封闭性。9证法证法2:设设L由正

9、则表达式由正则表达式r定义，对定义，对r的构造次数进行归纳证明：的构造次数进行归纳证明：（1）设）设r的构造次数为的构造次数为0，即，即r是是， 或者或者a,则则R=， R= ，a R= a，此时，此时rR和和r相同。相同。（2）设定理在）设定理在r的构造次数小于的构造次数小于k时成立，讨论时成立，讨论r的构造次数的构造次数等于等于k时，时，情况情况 设设r=r1+r2，其中，其中r1和和r2的构造次数都小于的构造次数都小于k，由归纳假设，可以构造由归纳假设，可以构造r1R和和r2R，使得，使得L(r1R)=L(r1)R，L(r2R)=L(r2)R，因为因为L(r)=L(r1) L(r2)，所

10、以，所以L(r)R=L(r1)R L(r2)R，因此因此r1R + r2R就是代表就是代表L(r)R的正则表达式。的正则表达式。情况情况 设设r=r1r2，其中，其中r1和和r2的构造次数都小于的构造次数都小于k，由归纳假设，可以构造由归纳假设，可以构造r1R和和r2R，使得，使得L(r1R)=L(r1)R，L(r2R)= L(r2)R，由于由于L(r)=L(r1)L(r2)，因此，因此L(r)R=L(r1)R L(r2)R，所以，所以r1Rr2R就是就是代表代表L(r)R的正则表达式。的正则表达式。10情况情况 设设r=r1*，其中，其中r1的构造次数小于的构造次数小于k，由归纳假设，可以构

11、造由归纳假设，可以构造r1R，使得，使得L（r1R）= L（r1）R，因为因为L（r）= L（r1）*，对于对于 w L（r），），w=w1w2wm，每个，每个wi L（r1）。）。wR= wmRwm-1Rw1R，其中每个，其中每个wiR L（r1）R，因此因此wR L（r1 R）*）。）。反之，反之， w L（r1 R）*），），w都有都有w1w2wn的形式，的形式，其中其中wi L（r1）R。因此，因此，wR= wnRwn-1Rw1R L（r1*）=L(r),因此（因此（r1 R）*就是代表就是代表L（r）R的正则表达式。的正则表达式。11例例3 设设L是由正则表达式（是由正则表达式（0+

12、1）0*表示的语言，根据连接规则表示的语言，根据连接规则可知可知LR是（是（0*）R（0+1）R表示的语言，而（表示的语言，而（0*）R=0*，0或或1的反的反转是它自身，转是它自身，即（即（0+1）R=（0+1），因此），因此LR的正则表达式为的正则表达式为0*（0+1）。）。定义定义4.2 假设假设 和和 是两个字母表。函数是两个字母表。函数 h：*如果对于如果对于 x,y，都有，都有h(xy)=h(x)h(y)，则称则称h为为 到到 *的同态映射（的同态映射（homomorphism）。）。对于对于L*， h（L）=h(x) * 称为称为L的同态像。的同态像。对于对于w*，h-1（ w）

13、=x|h(x)=w 称为称为w的同态原像。的同态原像。对于对于L*，h-1（L）=x|h(x) L 称为称为L的同态原像，的同态原像，并称并称h-1（L）为）为L的逆同态。的逆同态。12例例4 已知已知 0，1和和 a，b，c，定义，定义h为为 h(0)ab h(1)bcc那么那么h(010)abbccab。L00，010的同态像为的同态像为语言语言h(L)abab，abbccab。例例5 已知已知 0，1和和 a，b，c。同态映射。同态映射h为为 h(0)dbcc h(1)bbc如果如果L是正则语言，使用正则表达式是正则语言，使用正则表达式 r=(0+1*)1*表示，那么表示，那么 r1=(

14、dbcc+(bbc)*) (bbc)*表示的语言是正则语言表示的语言是正则语言h(L)。13 定理定理4.7 如果如果L是字母表是字母表 上的正则语言，上的正则语言， h是是 到到 上的同态映射，则上的同态映射，则h(L)也是也是 上的正则语言。即正则上的正则语言。即正则语言在同态运算上是封闭的。语言在同态运算上是封闭的。证明：证明：设设L是用正则表达式是用正则表达式r表示的正则语言。表示的正则语言。用用h(r)表示把表示把r中的每个符号中的每个符号a，用，用h(a)来代替后的来代替后的表达式。表达式。根据正则表达式的定义，根据正则表达式的定义，h(r)也是正则表达式。也是正则表达式。下面证明

15、下面证明h(r)定义的语言是定义的语言是h(L)，即即L(h(r)=h(L(r)。对对r的构造次数进行归纳：的构造次数进行归纳：14（1）设）设r的构造次数为的构造次数为0，即，即r是是， 或者或者a,当当r是是或者或者 时，时，L（r）中或者只含空串，或者没有串，此时）中或者只含空串，或者没有串，此时L(h(r)=L(r)，所以，所以L(h(r)=h(L(r)。当当r是是a时，时，L(r)=a，所以，所以h(L(r)=h(a )另一方面，另一方面，h(r)是由符号串是由符号串h(a )表示的表示的 上的正则表达式，因此上的正则表达式，因此L(h(r)=h(a)，所以所以L(h(r)=h(L(

16、r)。（2）设定理在）设定理在r的构造次数小于的构造次数小于k时成立，讨论时成立，讨论r的构造次数等于的构造次数等于k时，时，设设r=r1+r2，其中，其中r1和和r2都是构造次数都小于都是构造次数都小于k的正则表达式，的正则表达式，由同态的定义，有由同态的定义，有h(r) =h(r1+r2)= h(r1)+ h(r2)所以所以L(h(r)=L(h(r1)+ h(r2)= L(h(r1) L( h(r2)把把h作用到一个语言上时，相当于把它单独作用到语言的每一个字符串，作用到一个语言上时，相当于把它单独作用到语言的每一个字符串，因此因此 h(L(r)= h(L(r1) L(r2)= h(L(r

17、1) h(L(r2)由归纳假设，由归纳假设，L(h(r1)= h(L(r1)， L( h(r2)= h(L(r2)所以，有所以，有L(h(r)=h(L(r)。对于对于r=r1r2，和，和r=r1*，可以类似地证明，可以类似地证明15定理定理4.8 设设 h是字母表是字母表 到到 上的同态映射，上的同态映射， L是字母表是字母表 上的正则语言，则上的正则语言，则h-1(L)也是字母表也是字母表 上正则语言。即正上正则语言。即正则语言在逆同态运算上是封闭的。则语言在逆同态运算上是封闭的。（证明略）（证明略）定义定义4.3 设设L1和和L2是定义在同一个字母表上的语言，我是定义在同一个字母表上的语言

18、，我们称们称 L1/L2x|xy L1对于某个对于某个y L2 为为L1和和L2的的右商右商（right quotient）。）。 由定义可以看出，由定义可以看出， L1和和L2的右商中的符号串可以这样求的右商中的符号串可以这样求出：先找出出：先找出L1中所有其后缀属于中所有其后缀属于L2的符号串，由每个这的符号串，由每个这样的符号串去掉后缀后形成的符号串都属于样的符号串去掉后缀后形成的符号串都属于L1/L2。16例例6 设设 L1=anbm：n 1，m 0 ba L2bm：m 1L2中的符号串至少包含一个中的符号串至少包含一个b。因此，先找出。因此，先找出L1中其后缀为中其后缀为bt(t 1

19、)的串，这些串在的串，这些串在anbm：n 1，m 1中，将这些串中，将这些串去掉形为去掉形为bt( t 1)的后缀的后缀,得到得到 L1L2anbm：n 1，m 0 如果如果L1，L2是正则语言，是正则语言，L1L2还是正则的吗？还是正则的吗？定理定理4.9 如果如果L1和和L2是正则语言，那么是正则语言，那么L1L2也是正则语言。也是正则语言。即正则语言在右商运算上是封闭的。即正则语言在右商运算上是封闭的。证明：证明：设设M=(Q, , ，q0，F）是）是DFA，且，且L1=L(M)构造一个构造一个DFA M=(Q, , ，q0，F），），其中其中F=qi| qi Q且且 y L2，使得，

20、使得 （qi，y） F17下面证明下面证明L（M）L1L2，由由L1L2的定义，对的定义，对 x L1L2，一定存在，一定存在y L2，使得使得xy L1，即，即 （q0，xy） F因此，一定存在某个因此，一定存在某个q Q，使得，使得 （q0，x）=q并且并且 （q，y） F因此，根据构造可知因此，根据构造可知q F，并且，并且M接受接受x。 反之，对于反之，对于M接受的任意接受的任意x，我们都有，我们都有 （q0，x）=q F根据根据M的构造，一定存在一个的构造，一定存在一个y L2，满足满足 （q0，xy） F 。因此，因此，xy属于属于L1，x属于属于L1L2。得到。得到 L（M）=

21、L1L2所以，所以，L1L2是正则的。是正则的。18例例7 已知已知 L1L（a*baa*） L2L（ab*）求求L1L2。首先找到接受首先找到接受L1的的DFA如图，如图， Startq0q2baq1aaq3bba,b19定理定理4.9的方法构造的方法构造DFA M=(Q, , ，q0，F），），由于由于F=qi| qi Q且且 y L2，使得，使得 （qi，y） F从前图中可以看出，从前图中可以看出，q1，q2 F因此，接受因此，接受L1L2的自动机如下图。这个自动机接受由正的自动机如下图。这个自动机接受由正则表达式则表达式a*b+a*baa*表示的语言，将表示的语言，将a*b+a*baa

22、*简化成简化成a*ba*。因此。因此L1L2L（a*ba*）。）。 Startq0q2baaaq3bba,bq120正则代换正则代换(regular substitution) 设设、是两个字母表，映射是两个字母表，映射 *2:f被称为是从被称为是从到到的的代换代换。如果对于。如果对于 a，f(a)是是上的上的 RL RL ，则称，则称f f为为正则代换。正则代换。 21先将先将f的定义域扩展到的定义域扩展到*上：上： *2:*f f(f()=)= ； f(xa f(xa)=f(x)f(a)=f(x)f(a)。再将再将f的定义域扩展到的定义域扩展到*2*22:f对于对于 L *LxxfLf)(

23、)(22例例 8 设设=0，1，=a，b，f(0)=a，f(1)=b*，则则 f(010)=f(0)f(1)f(0)=ab*a f(11，00)=f(11)f(00) =f(1)f(1)f(0)f(0)=b*b*+aa=b*+aa f(L(0*(0+1)1*)=L(a*(a+b*)(b*)*) =L(a*(a+b*)b*)=L(a*ab*+a*b*b*) =L(a*b*) 23f f是正则代换是正则代换, ,则则 f()=； f()=； 对于对于 a，f(a)是是上的上的RERE； 如果如果r，s是是上的上的RERE，则，则 f(r+s)=f(r)+f(s) f(rs)=f(r)f(s) f(

24、r*)=f(r)* 是是上的上的RERE。 24定理定理 4.10 设设L是是上的一个上的一个 RL *2:f证明：证明：描述工具：描述工具：RE。对对r中运算符的个数中运算符的个数n施以归纳，证明施以归纳，证明f(r)是表示是表示f(L)的的RE。 当当n=0时时，结论成立。，结论成立。当当nk时定理成立时定理成立, ,即当即当r r中运算符的个数不大于中运算符的个数不大于k k时：时：f(L(r) = L(f(r)f(L(r) = L(f(r)。25当当n=k+1时，时， r=r1+r2。 f(L)=f(L(r) =f(L(r1+r2) =f(L(r1)L(r2)RERE的定义的定义 =f

25、(L(r1)f(L(r2)正则代换的定义正则代换的定义 =L(f(r1)L (f (r2)归纳假设归纳假设 =L(f(r1)+f (r2)RERE的定义的定义 =L(f(r1+r2)RERE的正则代换的定义的正则代换的定义 =L(f(r)26 r=r1r2。 f(L)=f(L(r) =f(L(r1r2) =f(L(r1) L(r2)RERE的定义的定义 =f(L(r1) f(L(r2)正则代换的定义正则代换的定义 =L(f(r1) L (f (r2)归纳假设归纳假设 =L(f(r1) f (r2)RERE的定义的定义 =L(f(r1r2) RERE的正则代换的定义的正则代换的定义 =L(f(r

26、)27 r=r1*。 f(L)=f(L(r) =f(L(r1*) =f(L(r1)*)RERE的定义的定义 =(f(L(r1)*正则代换的定义正则代换的定义 =(L(f(r1)*归纳假设归纳假设 =L(f(r1)*)RERE的定义的定义 =L(f(r1*)RERE的正则代换的定义的正则代换的定义 =L(f(r)28例例9 设设=0，1，2，=a=a，bb，正则代换，正则代换f f定义为：定义为： f(0)=ab； f(1)=b*a*； f(2)=a*(a+b)则：则： f(00)=abab； f(010)=abb*a*ab=ab+a+b； f(0+1+2)*)=(ab+b*a*+ a*(a+b

27、)*=(b*a*+a*(a+b)*=(a+b)*；29二、二、RL的泵引理的泵引理 泵引理泵引理(pumping lemma) 设设L为一个为一个 RL ，则存在仅依赖于，则存在仅依赖于L的正整数的正整数N，对于对于 zL，如果，如果|z|N，则存在，则存在u、v、w，满足，满足 z=uvw； |uv|N； |v|1； 对于任意的整数对于任意的整数i0，uviwL；30证明思想证明思想31例例 1 证明证明0n1n|n1不是不是 RL。 证明：证明： 假设假设L=0n1n|n1 是是 RL z=0N1N 按照泵引理所述按照泵引理所述 v=0kk1 此时有，此时有，u=0N-k-jw=0j1N

28、泵引理泵引理设设L为一个为一个 RL ，则存在仅，则存在仅依赖依赖于于L的正整数的正整数N，对于，对于 zL，如果，如果|z|N，则存在，则存在u、v、w，满足，满足 z=uvw； |uv|N； |v|1； 对于任意的整数对于任意的整数i0，uviwL；32从而有，从而有，uviw=0N-k-j(0k)i0j1N=0N+(i-1)k1N 当当i=2时，我们有：时，我们有：uv2w=0N+(2-1)k1N = 0N+k1N注意到注意到k1，所以，所以，N+kN。这就是说，这就是说，0N+k1N L这与泵引理矛盾。这与泵引理矛盾。所以，所以，L不是不是 RL。 泵引理泵引理设设L为一个为一个 RL

29、 ，则存在仅，则存在仅依赖依赖于于L的正整数的正整数N，对于，对于 zL，如果，如果|z|N，则存在，则存在u、v、w，满足，满足 z=uvw； |uv|N； |v|1； 对于任意的整数对于任意的整数i0，uviwL；33例例 2 证明证明0n|n为素数为素数不是不是 RL。 证明：假设证明：假设L=0n|n为素数为素数 是是 RL。 取取 z=0N+p L ，不妨设不妨设v=0k，k1 从而有，从而有，uviw=0N+p-k-j(0k)i0j=0N+p+(i-1)k泵引理泵引理设设L为一个为一个 RL ，则存在仅，则存在仅依赖依赖于于L的正整数的正整数N，对于，对于 zL，如果，如果|z|N

30、，则存在，则存在u、v、w，满足，满足 z=uvw； |uv|N； |v|1； 对于任意的整数对于任意的整数i0，uviwL；34当当i=N+p+1时，时，N+p+(i-1)k=N+p+(N+p+1-1)k = N+p+(N+p)k = (N+p)(1+k)注意到注意到k1，所以，所以N+p+(N+p+1-1)k=(N+p)(1+k)不是素数。故当不是素数。故当i=N+p+1时，时，uvN+p+1w=0(N+p)(1+k) L这与泵引理矛盾。这与泵引理矛盾。所以，所以，L不是不是 RL。 泵引理泵引理设设L为一个为一个 RL ，则，则存在仅依赖存在仅依赖于于L的正整的正整数数N，对于，对于 z

31、L，如，如果果|z|N，则存在，则存在u、v、w，满足，满足 z=uvw； |uv|N； |v|1； 对于任意的整数对于任意的整数i0，uviwL；35例例 3 证明证明0n1m2n+m|m，n1不是不是 RL。 证明：假设证明：假设L=0n1m2n+m|m，n1 是是 RL。 取取z=0N1N22N 设设 v=0k k1 从而有，从而有，uviw=0N-k-j(0k)i0j1N22N=0N+(i-1)k1N22N36uv0w=0N+(0-1)k1N22N= 0N-k1N22N 注意到注意到k1，N-k+N=2N-k|*/RL |。70如果如果(q，a)=p，f(q)= x，必有，必有f(p)

32、=xa qQ，如果，如果，f(q)=f(q0，x)=x所以，所以， a，如果，如果，p=(q，a)=(q0，x)，a)=(q0，xa)则则f(p)=f(q，a)= f(q0，x)，a)=f(q0，xa)=xa即，如果即，如果M在状态在状态q读入字符读入字符a时进入状态时进入状态p，则则M在在q对应的状态对应的状态f(q0，x)=x读入字读入字符符 a 时 ， 进 入时 ， 进 入 p 对 应 的 状 态对 应 的 状 态 f ( ( q0，xa) )=xa。所以，。所以，f是是M和和M之间的同构之间的同构映射。映射。 71DFA的极小化的极小化 可以区分的可以区分的(distinguishab

33、le) 状态状态设设DFA M=(Q，q0，F)，如果，如果 x*， 对对Q中的两个状态中的两个状态q和和p，使得，使得(q，x)F 和和(p，x)F中，有且仅有一个成立，则中，有且仅有一个成立，则称称p和和q是是可以可以区分区分的的。否则，称。否则，称q和和p等价。并记作等价。并记作qp 。72算法算法1 DFA的极小化算法的极小化算法算法思想：扫描所有的状态对，找出所有的可区算法思想：扫描所有的状态对，找出所有的可区分的状态对，不可取分的状态对一定是等价的。分的状态对，不可取分的状态对一定是等价的。输入：给定的输入：给定的DFA。输出：可区分状态表。输出：可区分状态表。主要数据结构：状态对

34、的关联链表；可区分状态主要数据结构：状态对的关联链表；可区分状态表。表。 73主要步骤主要步骤 for (q，p)F(Q-F) do标记可区分状态表中的表项标记可区分状态表中的表项(q，p)； for (q, ,p)FF(Q-F) (Q-F)&qp doif a，可区分状态表中的表项，可区分状态表中的表项(q, ,a)，(p, ,a)已被标记已被标记 thenbegin 标记可区分状态表中的表项标记可区分状态表中的表项(q,p)；递归地标记本次被标记的状态对的递归地标记本次被标记的状态对的关联链表上的各个状态对在可区分状态表中的对关联链表上的各个状态对在可区分状态表中的对应表项应表项e

35、nd 74else for a，doi f ( q , , a ) ( p , , a ) & ( q , , p ) 与与(q, ,a),(p, ,a)不是同一个状态对不是同一个状态对 then将将(q, ,p)放在放在(q, ,a),(p, ,a)的关的关联链表上。联链表上。 75定理定理2 对于任意对于任意DFA M=(Q，q0，F)，Q中中的两个状态的两个状态q和和p是可区分的充要条件是是可区分的充要条件是(q，p)在在DFA的极小化算法中被标记。的极小化算法中被标记。证明：证明： 先证必要性。先证必要性。设设q和和p是可区分的，是可区分的，x是区分是区分q和和p的最短字符串。

36、的最短字符串。现施归纳现施归纳于于x的长度，证明的长度，证明(q，p)一定被算法标记。一定被算法标记。 76当当|x|=0时时区分区分q和和p，表明，表明q和和p有且仅有一个为有且仅有一个为M的终的终止状态，所以，止状态，所以，(q, ,p)F(Q-F)因此，它在算法的第因此，它在算法的第(1)行被标记。行被标记。 设当设当|x|=n时结论成立时结论成立x是区分是区分q和和p的长度为的长度为n的字符串，则的字符串，则(q, ,p)被算被算法标记。法标记。 77当当|x|=n+1时时 设设x=ay，其中，其中|y|=n。由于。由于x是区分是区分q和和p的最短的最短的字符串，所以，的字符串，所以，

37、(q，x)F 和和(p，x)F中，有且仅有一个成立。不妨假设：中，有且仅有一个成立。不妨假设：(q, ,x) F ，(p, ,x)F即即(q, ,a)，y) F ，(p, ,a)，y)F设设(q, ,a)=u，(p, ,a)=v y是区分是区分u和和v的长度为的长度为n的字符串。的字符串。 78由归纳假设，由归纳假设，(u, ,v)可以被算法标记可以被算法标记。如果在考察如果在考察(q, ,p)时，时，(u, ,v)已经被标记，则已经被标记，则(q, ,p)在算法的第在算法的第(4)行被标记；行被标记；如果在考察如果在考察(q, ,p)时，时，(u, ,v)还没有被标记，则还没有被标记，则(q

38、, ,p)在算法的第在算法的第(7)行被放入到行被放入到(u, ,v)的关联链的关联链表中，而当表中，而当(u, ,v)被标记时，在算法的第被标记时，在算法的第(5)行行在在“递归递归”过程中过程中(q, ,p)被标记。被标记。结论对结论对|x|=n+1成立。成立。 79充分性。充分性。 设设(q, ,p)在算法中被标记。对它被标记的顺序在算法中被标记。对它被标记的顺序n施施归纳，证明归纳，证明q和和p是可区分的。是可区分的。 令令|F(Q-F)|=m，显然，当，显然，当1nm时，时，(q, ,p)是在算法的第是在算法的第(1)行被标记的，此时，行被标记的，此时，是区分是区分q和和p的字符串：

39、的字符串：(q,)F 和和(p,)F有且仅有一个成立。有且仅有一个成立。 80设设nk(km)时结论成立。即，如果时结论成立。即，如果 (q, ,p)是被算是被算法在第法在第k个或者第个或者第k个之前标记的，则存在字符串个之前标记的，则存在字符串x，x区分区分q和和p。即：。即：(q, ,x)F 和和(p, ,x)F有有且仅有一个成立。且仅有一个成立。 当当n=k+1时，如果时，如果(q, ,p)是在算法的第是在算法的第(4)行被标记的，行被标记的，此时，此时，(q, ,a)，(p, ,a)一定是在第一定是在第k个之前被个之前被标记的。设标记的。设(q, ,a)=u，(p, ,a)=v，由归纳

40、假设，由归纳假设，存在字符串存在字符串x，x区分区分u和和v：(u, ,x)F 和和(v, ,x)F有且仅有一个成立，从而，有且仅有一个成立，从而，(q, ,ax)F 和和(p, ,ax)F有且仅有一个成立。即，有且仅有一个成立。即，ax是区分是区分q和和p的字符串。的字符串。 81如果如果(q, ,p)是在算法的第是在算法的第(5)行被标记的，则它必在某行被标记的，则它必在某个状态对个状态对(u, ,v)的关联链表中，而的关联链表中，而(u, ,v)必在必在(q, ,p)之之前被标记。由归纳假设，存在前被标记。由归纳假设，存在x区分区分(u, ,v)；存在存在a，(q, ,a)=u，(p,

41、,a)=v使得使得(q, ,p)被放在被放在(u, ,v)的关联链表中；的关联链表中；ax是区分是区分q和和p的字符串。的字符串。所以，结论对所以，结论对n=k+1成立。由归纳法原理，结论对所成立。由归纳法原理，结论对所有有的的n成立。成立。 82定理定理3 由算法由算法1构造的构造的DFA在去掉不可达状态是在去掉不可达状态是最小最小DFA 。证明：证明：设设M=(Q,q0, ,F)为算法为算法5-1的输入的输入DFA，M=(Q/,q0, ,F)是相应的输出是相应的输出DFA。F=q|qF。对于对于 qQ/， aa，定义，定义(q，a)=(q, ,a) 83的相容性。的相容性。设设q=p ，也

42、就是说，也就是说，q和和p等价：等价：qp。即。即根据算法根据算法1，状态，状态q和和p是不可区分的是不可区分的(未被算未被算法标记法标记)。此时，对于此时，对于 aa，必须有，必须有(q, ,a)(p, ,a)。否则，状态对否则，状态对(q, ,a)，(p, ,a)必定被算法必定被算法标记，从而最终导致标记，从而最终导致(q, ,p)被算法标记。被算法标记。此与此与qp矛盾。所以，状态矛盾。所以，状态(q, ,a)和状态和状态(p, ,a) 等价：等价：(q, ,a)=(p, ,a)。所以，所以，的定义是相容的。的定义是相容的。 84L(M)=L(M) 。对对 x*，现施归纳于，现施归纳于|

43、x|，证明，证明(q0，x)=(q0，x) |x|=0 (q0,)=q0=(q0,) xx*并且并且|x|=n，(q0，xa)=(q0, ,x)，a)=(q0, ,x)，a) =(q0, ,x)，a) =(q0, ,xa) 由归纳法原理，结论对由归纳法原理，结论对 x*成立。成立。 85再由F的定义，(q0,x)=(q0,x)F (q0,x)F。所以，xL(M) xL(M)。即：L(M)=L(M)。 86证明所构造的证明所构造的M去掉不可达状态后是最小去掉不可达状态后是最小DFA。如果如果qp，则对于，则对于 xset(q)， yset(p)，x RL y不成立。不成立。事实上，如果事实上，如果qp，则存在则存在z*，z区分区分q和和p，有，有(q, ,z)=q 和和(p, ,z)= p有且仅有一个是终止状态，这就是有且仅有一个是终止状态，这就是说，说，xz和和yz有且仅有一个是有且仅有一个是L的句子。的句子。所以，所以，x RL y是不成立的。是不