《形式语言与自动机理论电子教案-05.ppt》由会员分享，可在线阅读，更多相关《形式语言与自动机理论电子教案-05.ppt（106页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第5章章 RL的性质的性质 RL性质性质 泵引理及其应用泵引理及其应用 并、乘积、闭包、补、交并、乘积、闭包、补、交正则代换、同态、逆同态的封闭性正则代换、同态、逆同态的封闭性 从从RLRL固有特征寻求表示的一致性固有特征寻求表示的一致性Myhill-NerodeMyhill-Nerode定理定理FAFA的极小化的极小化 RLRL的几个判定问题的几个判定问题空否、有穷否、两个空否、有穷否、两个DFADFA等价否、成员关系等价否、成员关系 12/18/202215.1 RL5.1 RL的泵引理的泵引理 泵引理泵引理(pumping lemma)设设L为为一一个个 RL，则则存存在在仅仅依依赖赖
2、于于L的的正正整整数数N，对对于于 zL，如如果果|z|N，则则存存在在u、v、w，满足，满足 z=uvw；|uv|N；|v|1；对于任意的整数对于任意的整数i0，uviwL；N不大于接受不大于接受L的最小的最小DFA M的状态数。的状态数。12/18/202225.1 RL5.1 RL的泵引理的泵引理证明思想证明思想12/18/202235.1 RL5.1 RL的泵引理的泵引理 证明：证明：DFA在在处处理理一一个个足足够够长长的的句句子子的的过过程程中中，必必定定会会重重复复地地经经过过某某一一个个状状态态。换换句句话话说说，在在DFA的的状状态态转转移移图图中中，必必定定存存在在一一条条
3、含含有有回回路路的的从从启启动动状状态态到到某某个个终终止止状状态态的的路路。由由于于是是回回路路，所所以以，DFA可可以以根根据据实实际际需需要要沿沿着着这这个个回回路路循循环环运运行行，相相当当于于这这个个回回路路中中弧弧上上的的标标记记构构成的非空子串可以重复任意多次。成的非空子串可以重复任意多次。12/18/202245.1 RL5.1 RL的泵引理的泵引理 M=(Q，q0，F)|Q|=N z=a1a2ammN (q0，a1a2ah)=qh 状状态态序序列列q0，q1，qN中中，至至少少有有两两个个状状态态是相同：是相同：qk=qj 12/18/202255.1 RL5.1 RL的泵引
4、理的泵引理 (q0，a1a2ak)=qk(qk，ak+1aj)=qj=qk(qj，aj+1am)=qm对于任意的整数对于任意的整数i0(qk，(ak+1aj)i)=(qk，(ak+1aj)i-1)=(qk，ak+1aj)=qk 12/18/202265.1 RL5.1 RL的泵引理的泵引理 故，故，(q0，a1a2ak(ak+1aj)i aj+1am)=qm也就是说，也就是说，a1a2ak(ak+1aj)i aj+1amL(M)u=a1a2ak，v=ak+1aj，w=aj+1am uviwL 12/18/202275.1 RL5.1 RL的泵引理的泵引理 例例 5-1 5-1 证明证明0n1n
5、|n1不是不是 RL。证明：证明：假设假设L=0n1n|n1 是是 RL z=0N1N 按照泵引理所述按照泵引理所述 v=0kk1 此时有，此时有，u=0N-k-jw=0j1N 12/18/202285.1 RL5.1 RL的泵引理的泵引理 从而有，从而有，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。12/18/202295.1 RL5.1 RL的泵引理的泵
6、引理 例例 5-2 5-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)k12/18/2022105.1 RL5.1 RL的泵引理的泵引理 当当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
7、+p)(1+k)L这与泵引理矛盾。所以，这与泵引理矛盾。所以，L不是不是 RL。12/18/2022115.1 RL5.1 RL的泵引理的泵引理例例 5-3 5-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)k1N22N12/18/2022125.1 RL5.1 RL的泵引理的泵引理uv0w=0N+(0-1)k1N22N=0N-k1N22N 注意到注意到k1，N-k+N=2N-k|*/RL|。12/1
8、8/2022785.3.1 Myhill-Nerode 5.3.1 Myhill-Nerode 定理定理如果如果(q，a)=p，f(q)=x，必有，必有f(p)=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之间的同构映
9、射。之间的同构映射。12/18/2022795.3.2 DFA5.3.2 DFA的极小化的极小化 可以区分的可以区分的(distinguishable)状态状态设设DFA M=(Q，q0，F)，如果，如果 x*，对对Q中的两个状态中的两个状态q和和p，使得，使得(q，x)F 和和(p，x)F中，有且仅有一中，有且仅有一个成立，则称个成立，则称p和和q是是可以区分的可以区分的。否则，。否则，称称q和和p等价。并记作等价。并记作qp 。12/18/2022805.3.2 DFA5.3.2 DFA的极小化的极小化算法算法5-1 DFA的极小化算法的极小化算法算算法法思思想想：扫扫描描所所有有的的状状
10、态态对对，找找出出所所有有的的可可区区分分的的状状态态对对，不不可可取取分分的的状状态态对对一一定是等价的。定是等价的。输入：给定的输入：给定的DFA。输出：可区分状态表。输出：可区分状态表。主要数据结构：状态对的关联链表；可区主要数据结构：状态对的关联链表；可区分状态表。分状态表。12/18/2022815.3.2 DFA5.3.2 DFA的极小化的极小化主要步骤主要步骤 for (q，p)F(Q-F)do标记可区分状态表中的表项标记可区分状态表中的表项(q，p)；for(q,p)FF(Q-F)(Q-F)&qp do if if a，可区分状态表中的表项，可区分状态表中的表项(q，a)，(p
11、，a)已被标记已被标记 thenthenbeginbegin标记可区分状态表中的表项标记可区分状态表中的表项(q(q，p)p)；递递归归地地标标记记本本次次被被标标记记的的状状态态对对的的关关联联链链表表上上的各个状态对在可区分状态表中的对应表项的各个状态对在可区分状态表中的对应表项end end 12/18/2022825.3.2 DFA5.3.2 DFA的极小化的极小化else for a，doif (q，a)(p，a)&(q，p)与与(q，a)，(p，a)不是同一个状态对不是同一个状态对 then将将(q，p)放在放在(q，a)，(p，a)的关联链表上。的关联链表上。12/18/2022
12、835.3.2 DFA5.3.2 DFA的极小化的极小化定理定理5-85-8 对于任意对于任意DFA M=(Q，q0，F)，Q中的两个状态中的两个状态q和和p是可区分的充要条是可区分的充要条件是件是(q，p)在在DFA的极小化算法中被标记。的极小化算法中被标记。证明：证明：先证必要性。先证必要性。设设q和和p是可区分的，是可区分的，x是区分是区分q和和p的最短字符串。的最短字符串。现施归纳于现施归纳于x的长度，证明的长度，证明(q，p)一定被算法标记。一定被算法标记。12/18/2022845.3.2 DFA5.3.2 DFA的极小化的极小化当当|x|=0时时区区分分q和和p，表表明明q和和p
13、有有且且仅仅有有一一个个为为M的的终止状态，所以，终止状态，所以，(q，p)F(Q-F)因此，它在算法的第因此，它在算法的第(1)行被标记。行被标记。设当设当|x|=n时结论成立时结论成立x是区分是区分q和和p的长度为的长度为n的字符串，则的字符串，则(q，p)被算法标记。被算法标记。12/18/2022855.3.2 DFA5.3.2 DFA的极小化的极小化当当|x|=n+1时时 设设x=ay，其其中中|y|=n。由由于于x是是区区分分q和和p的的最最短短的的字字符符串串，所所以以，(q，x)F 和和(p，x)F中，有且仅有一个成立。不妨假设：中，有且仅有一个成立。不妨假设：(q，x)F，(
14、p，x)F即即(q，a)，y)F，(p，a)，y)F设设(q，a)=u，(p，a)=v y是区分是区分u和和v的长度为的长度为n的字符串。的字符串。12/18/2022865.3.2 DFA5.3.2 DFA的极小化的极小化由归纳假设，由归纳假设，(u，v)可以被算法标记可以被算法标记。如果在考察如果在考察(q，p)时，时，(u，v)已经被标记，已经被标记，则则(q，p)在算法的第在算法的第(4)行被标记；行被标记；如果在考察如果在考察(q，p)时，时，(u，v)还没有被标记，还没有被标记，则则(q，p)在算法的第在算法的第(7)行被放入到行被放入到(u，v)的关联链表中，而当的关联链表中，而
15、当(u，v)被标记时，在算被标记时，在算法的第法的第(5)行在行在“递归递归”过程中过程中(q，p)被标被标记。记。结论对结论对|x|=n+1成立。成立。12/18/2022875.3.2 DFA5.3.2 DFA的极小化的极小化充分性。充分性。设设(q，p)在算法中被标记。对它被标记的顺在算法中被标记。对它被标记的顺序序n施归纳，证明施归纳，证明q和和p是可区分的。是可区分的。令令|F(Q-F)|=m，显显然然，当当1nm时时，(q，p)是是在在算算法法的的第第(1)行行被被标标记记的的，此此时时，是区分是区分q和和p的字符串：的字符串：(q，)F 和和(p，)F有且仅有一个成立。有且仅有一
16、个成立。12/18/2022885.3.2 DFA5.3.2 DFA的极小化的极小化设设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，由归纳假设，存在字符串由归纳假设，存在字符串x，x区分
17、区分u和和v：(u，x)F 和和(v，x)F有且仅有一个成立，从而，有且仅有一个成立，从而，(q，ax)F 和和(p，ax)F有且仅有一个成立。即，有且仅有一个成立。即，ax是区分是区分q和和p的字符串。的字符串。12/18/2022895.3.2 DFA5.3.2 DFA的极小化的极小化如如果果(q，p)是是在在算算法法的的第第(5)行行被被标标记记的的，则则它它必必在在某某个个状状态态对对(u，v)的的关关联联链链表表中中，而而(u，v)必必在在(q，p)之之前前被被标标记记。由由归归纳纳假假设，存在设，存在x区分区分(u，v)；存存在在a，(q，a)=u，(p，a)=v使使得得(q，p)
18、被被放放在在(u，v)的的关关联联链链表表中中；ax是是区区分分q和和p的字符串。的字符串。所以，结论对所以，结论对n=k+1成立。由归纳法原理，成立。由归纳法原理，结论对所有的结论对所有的n成立。成立。12/18/2022905.3.2 DFA5.3.2 DFA的极小化的极小化定理定理5-9 5-9 由算法由算法5-1构造的构造的DFA在去掉不在去掉不可达状态是最小可达状态是最小DFA 。证明：证明：设设M=(Q,q0,F)为为算算法法5-1的的输输入入DFA，M=(Q/,q0,F)是是相相应应的的输输出出DFA。F=q|qF。对于对于 qQ/，a a，定义，定义(q，a)=(q，a)12/
19、18/2022915.3.2 DFA5.3.2 DFA的极小化的极小化的相容性。的相容性。设设q=p，也就是说，也就是说，q和和p等价：等价：qp。即。即根据算法根据算法5-1，状态，状态q和和p是不可区分的是不可区分的(未被算未被算法标记法标记)。此时，对于。此时，对于 aa，必须有，必须有(q，a)(p，a)。否则，状态对。否则，状态对(q，a)，(p，a)必定被算法标记，从而最终导致必定被算法标记，从而最终导致(q，p)被算法被算法标记。此与标记。此与qp矛盾。所以，状态矛盾。所以，状态(q，a)和和状态状态(p，a)等价：等价：(q，a)=(p，a)。所。所以，以，的定义是相容的。的定
20、义是相容的。12/18/2022925.3.2 DFA5.3.2 DFA的极小化的极小化L(M)=L(M)。对对 x*，现施归纳于，现施归纳于|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*成立。成立。12/18/2022935.3.2 DFA5.3.2 DFA的极小化的极小化再由F的定义，(q0，x)=(q0，x)F(q0，x)F。所以，xL(M)xL(M)。即：L(M)=L(M)。12/18/2
21、022945.3.2 DFA5.3.2 DFA的极小化的极小化证明所构造的证明所构造的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是不成立的。是不成立的。12/18/2022955.3.2 DFA5.3.2 DFA的极小化的极小化例例5-1
22、15-11 用算法用算法5-1对图对图5-4所给的所给的DFA进行进行极小化。极小化。q1q2 q3 q4 q5 q0q1q2q3q412/18/2022965.3.2 DFA5.3.2 DFA的极小化的极小化12/18/2022975.3.2 DFA5.3.2 DFA的极小化的极小化例例5-115-11 用算法用算法5-1对图对图5-7所给的所给的DFA进行进行极小化。极小化。12/18/2022985.3.2 DFA5.3.2 DFA的极小化的极小化q1q2q3q4q5q6q7q8q0q1q2q3q4q5q6q712/18/2022995.4 5.4 关于正则语言的判定算法关于正则语言的判
23、定算法 定理定理 5-10 5-10 设设DFA M=(Q，q0，F)，L=L(M)非空的充分必要条件是：存在非空的充分必要条件是：存在x*，|x|Q|，(q0，x)F。证明：充分性显然。证明：充分性显然。必要性：必要性：M的状态转移图中必存在一条从的状态转移图中必存在一条从q0到某一个终止状态到某一个终止状态qf且无且无重复状态的路，此重复状态的路，此路中的状态数路中的状态数n|Q|。此路的标记。此路的标记x满足满足|x|n-1。而。而(q0，x)F。即。即x是是L=L(M)的的长度小于长度小于|Q|的句子。的句子。12/18/20221005.4 5.4 关于正则语言的判定算法关于正则语言
24、的判定算法 定理定理5-115-11设设DFA M=(Q，q0，F)，L=L(M)为无穷的充分必要条件是：存在为无穷的充分必要条件是：存在x*，|Q|x|2|Q|，(q0，x)F。算法通过判定是否存在算法通过判定是否存在x*，|Q|x|2|Q|，(q0，x)F即可。即可。12/18/20221015.4 5.4 关于正则语言的判定算法关于正则语言的判定算法 定理定理 5-12 5-12 设设DFA M1=(Q1，1，q01，F1)，DFA M2=(Q2，2，q02，F2)，则存在判定则存在判定M1与与 M2是否等价的算法。是否等价的算法。通过判定两个通过判定两个DFADFA的极小的极小DFAD
25、FA是否同构就是否同构就可以判定它们是否等价。可以判定它们是否等价。12/18/20221025.4 5.4 关于正则语言的判定算法关于正则语言的判定算法 定理定理 5-13 设设L是字母表是字母表上的上的 RL，对任意，对任意x*，存在判定，存在判定x是不是是不是L的句子的算法。的句子的算法。从一定的意义上讲，接受从一定的意义上讲，接受L的的DFA M就是判就是判定定x是否是否L的一个桔子的的一个桔子的“算法算法”。12/18/20221035.5 5.5 小结小结 本本章章讨讨论论了了RL的的性性质质。包包括括：RL 的的泵泵引引理理，RL 关关于于并并、乘乘积积、闭闭包包、补补、交交、正
26、正则则代代换换、同同态态、逆逆同同态态等等运运算算的的封封闭闭性性。Myhill-Nerode定理与定理与FA的极小化。的极小化。泵引理。泵引理是用泵引理。泵引理是用RL的必要条件来用来的必要条件来用来证明一个语言不是证明一个语言不是 RL 的。它不能用来证明的。它不能用来证明一个语言是一个语言是 RL，而且是采用反证法。，而且是采用反证法。12/18/20221045.5 5.5 小结小结 RL 对对有有关关运运算算的的封封闭闭性性。RL 在在并并、乘乘、闭闭包包、补补、交交、正正则则代代换换、同同态态映映射射运运算算下是有效封闭的。下是有效封闭的。RL 的同态原像是的同态原像是 RL。设设 L1、L2*，如如果果L1是是 RL，则则L1/L2也也是是 RL。12/18/20221055.5 5.5 小结小结 如如果果L是是RL，则则根根据据RL确确定定的的*的的等等价价类类可可以以构构造造出出接接受受L的的最最小小DFA。更更方方便便的的方方法法是是通通过过确确定定给给定定DFA状状态态的的可可区区分分性性构造出等价的最小构造出等价的最小DFA。存存在在判判定定L(M)是是非非空空、M1与与 M2是是否否等等价价、L(M)是是否否无无穷穷、x是是不不是是RL L的的句句子子的的算算法。法。12/18/2022106