形式语言与自动机理论--第五章(蒋宗礼)

形式语言与自动机理论FormalLanguagesandAutomataTheory蒋宗礼课程目的和基本要求•课程性质–技术基础•基础知识要求–数学分析（或者高等数学），离散数学•主要特点–抽象和形式化–理论证明和构造性–基本模型的建立与性质课程目的和基本要求•本专业人员4种基本的专业能力–计算思维能力–算法的设计与分析能力–程序设计和实现能力–计算机软硬件系统的认知、分析、设计与应用能力•计算思维能力–逻辑思维能力和抽象思维能力–构造模型对问题进行形式化描述–理解和处理形式模型课程目的和基本要求•知识–掌握正则语言、下文无关语言的文法、识别模型及其基本性质、图灵机的基本知识。•能力–培养学生的形式化描述和抽象思维能力。–使学生了解和初步掌握“问题、形式化描述、自动化（计算机化）”这一最典型的计算机问题求解思路。主要内容•语言的文法描述。•RL–RG、FA、RE、RL的性质。•CFL–CFG(CNF、GNF)、PDA、CFL的性质。•TM–基本TM、构造技术、TM的修改。•CSL–CSG、LBA。教材及主要参考书目1.蒋宗礼，姜守旭.形式语言与自动机理论.北京：清华大学出版社，2003年2.JohnEHopcroft,RajeevMotwani,JeffreyDUllman.IntroductiontoAutomataTheory,Languages,andComputation(2ndEdition).Addison-WesleyPublishingCompany,20013.JohnEHopcroft,JeffreyDUllman.IntroductiontoAutomataTheory,Languages,andComputation.Addison-WesleyPublishingCompany,1979第5章RL的性质•RL性质–泵引理及其应用–并、乘积、闭包、补、交–正则代换、同态、逆同态的封闭性•从RL固有特征寻求表示的一致性–Myhill-Nerode定理–FA的极小化•RL的几个判定问题–空否、有穷否、两个DFA等价否、成员关系5.1RL的泵引理•泵引理(pumpinglemma)设L为一个RL，则存在仅依赖于L的正整数N，对于z∈L，如果|z|≥N，则存在u、v、w，满足⑴z=uvw；⑵|uv|≤N；⑶|v|≥1；⑷对于任意的整数i≥0，uviw∈L；⑸N不大于接受L的最小DFAM的状态数。5.1RL的泵引理•证明思想5.1RL的泵引理证明：DFA在处理一个足够长的句子的过程中，必定会重复地经过某一个状态。换句话说，在DFA的状态转移图中，必定存在一条含有回路的从启动状态到某个终止状态的路。由于是回路，所以，DFA可以根据实际需要沿着这个回路循环运行，相当于这个回路中弧上的标记构成的非空子串可以重复任意多次。5.1RL的泵引理M=(Q，∑，δ，q0，F)|Q|=Nz=a1a2…amm≥Nδ(q0，a1a2…ah)=qh状态序列q0，q1，…，qN中，至少有两个状态是相同：qk=qj5.1RL的泵引理δ(q0，a1a2…ak)=qkδ(qk，ak+1…aj)=qj=qkδ(qj，aj+1…am)=qm对于任意的整数i≥0δ(qk，(ak+1…aj)i)=δ(qk，(ak+1…aj)i-1)…=δ(qk，ak+1…aj)=qk5.1RL的泵引理故，δ(q0，a1a2…ak(ak+1…aj)iaj+1…am)=qm也就是说，a1a2…ak(ak+1…aj)iaj+1…am∈L(M)u=a1a2…ak，v=ak+1…aj，w=aj+1…amuviw∈L5.1RL的泵引理•例5-1证明{0n1n|n≥1}不是RL。证明：假设L={0n1n|n≥1}是RLz=0N1N按照泵引理所述v=0kk≥1此时有，u=0N-k-jw=0j1N5.1RL的泵引理从而有，uviw=0N-k-j(0k)i0j1N=0N+(i-1)k1N当i=2时，我们有：uv2w=0N+(2-1)k1N=0N+k1N注意到k≥1，所以，N+kN。这就是说，0N+k1NL这与泵引理矛盾。所以，L不是RL。5.1RL的泵引理•例5-2证明{0n|n为素数}不是RL。证明：假设L={0n|n为素数}是RL。取z=0N+p∈L，不妨设v=0k，k≥1从而有，uviw=0N+p-k-j(0k)i0j=0N+p+(i-1)k5.1RL的泵引理当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)注意到k≥1，所以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。5.1RL的泵引理•例5-3证明{0n1m2n+m|m，n≥1}不是RL。证明：假设L={0n1m2n+m|m，n≥1}是RL。取z=0N1N22N设v=0kk≥1从而有，uviw=0N-k-j(0k)i0j1N22N=0N+(i-1)k1N22N5.1RL的泵引理uv0w=0N+(0-1)k1N22N=0N-k1N22N注意到k≥1，N-k+N=2N-k2N0N-k1N22NL这个结论与泵引理矛盾。所以，L不是RL。5.1RL的泵引理•用来证明一个语言不是RL•不能用泵引理去证明一个语言是RL。⑴由于泵引理给出的是RL的必要条件，所以，在用它证明一个语言不是RL时，我们使用反证法。⑵泵引理说的是对RL都成立的条件，而我们是要用它证明给定语言不是RL，这就是说，相应语言的“仅仅依赖于L的正整数N”实际上是不存在的。所以，我们一定是无法给出一个具体的数的。因此，人们往往就用符号N来表示这个“假定存在”、而实际并不存在的数。5.1RL的泵引理⑶由于泵引理指出，如果L是RL，则对任意的z∈L，只要|z|≥N，一定会存在u、v、w，使uviw∈L对所有的i成立。因此，我们在选择z时，就需要注意到论证时的简洁和方便。⑷当一个特意被选来用作“发现矛盾”的z确定以后，就必须依照|uv|≤N和|v|≥1的要求，说明v不存在(对“存在u、v、w”的否定)。5.1RL的泵引理⑸与选z时类似，在寻找i时，我们也仅需要找到一个表明矛盾的“具体”值就可以了(对“所有i”的否定)。⑹一般地，在证明一个语言不是RL的时候，我们并不使用泵引理的第(5)条。⑺事实上，引理所要求的|uv|≤N并不是必须的。这个限制为我们简化相应的证明提供了良好支撑——扩充了的泵引理。5.2RL的封闭性•封闭性(closureproperty)如果任意的、属于同一语言类的语言在某一特定运算下所得的结果仍然是该类语言，则称该语言类对此运算是封闭的•有效封闭性(validclosureproperty)给定一个语言类的若干个语言的描述，如果存在一个算法，它可以构造出这些语言在给定运算下所获得的运算结果的相应形式的语言描述，则称此语言类对相应的运算是有效封闭的。5.2RL的封闭性定理5-1RL在并、乘积、闭包运算下是封闭的。•根据RE的定义，立即可以得到此定理。5.2RL的封闭性定理5-2RL在补运算下是封闭的。证明：M=(Q，∑，δ，q0，F)L(M)=L，取DFAM′=(Q，∑，δ，q0，Q-F)显然，对于任意的x∈∑*，δ(q0，x)=f∈Fδ(q0，x)=fQ-F即：x∈L(M)xL(M′)，L(M′)=∑*-L(M)。所以，RL在补运算下是封闭的。定理得到证明。5.2RL的封闭性定理5-3RL在交运算下封闭。证明思路5.2RL的封闭性•正则代换(regularsubstitution)设∑、Δ是两个字母表，映射*2:f被称为是从∑到Δ的代换。如果对于a∈∑，f(a)是Δ上的RL，则称f为正则代换。5.2RL的封闭性•先将f的定义域扩展到∑*上：*2:*f⑴f(ε)={ε}；⑵f(xa)=f(x)f(a)。5.2RL的封闭性•再将f的定义域扩展到*2**22:f对于L∑*LxxfLf)()(5.2RL的封闭性•例5-4设∑={0，1}，Δ={a，b}，f(0)=a，f(1)=b*，则f(010)=f(0)f(1)f(0)=ab*af({11，00})=f(11)∪f(00)=f(1)f(1)∪f(0)f(0)=b*b*+aa=b*+aaf(L(0*(0+1)1*))=L(a*(a+b*)(b*)*)=L(a*(a+b*)b*)=L(a*ab*+a*b*b*)=L(a*b*)5.2RL的封闭性•f是正则代换,则⑴f(Φ)=Φ；⑵f(ε)=ε；⑶对于a∈∑，f(a)是Δ上的RE；⑷如果r，s是∑上的RE，则f(r+s)=f(r)+f(s)f(rs)=f(r)f(s)f(r*)=f(r)*是Δ上的RE。5.2RL的封闭性定理5-4设L是∑上的一个RL*2:f是正则代换，则f(L)也是RL。证明：描述工具：RE。对r中运算符的个数n施以归纳，证明f(r)是表示f(L)的RE。5.2RL的封闭性•当n=0时，结论成立。•当n≤k时定理成立,即当r中运算符的个数不大于k时：f(L(r))=L(f®。•当n=k+1时，5.2RL的封闭性⑴r=r1+r2。f(L)=f(L(r))=f(L(r1+r2))=f(L(r1)∪L(r2))RE的定义=f(L(r1))∪f(L(r2))正则代换的定义=L(f(r1))∪L(f(r2))归纳假设=L(f(r1)+f(r2))RE的定义=L(f(r1+r2))RE的正则代换的定义=L(f(r))5.2RL的封闭性⑵r=r1r2。f(L)=f(L(r))=f(L(r1r2))=f(L(r1)L(r2))RE的定义=f(L(r1))f(L(r2))正则代换的定义=L(f(r1))L(f(r2))归纳假设=L(f(r1)f(r2))RE的定义=L(f(r1r2))RE的正则代换的定义=L(f(r))5.2RL的封闭性⑶r=r1*。f(L)=f(L(r))=f(L(r1*))=f(L(r1)*)RE的定义=(f(L(r1)))*正则代换的定义=(L(f(r1)))*归纳假设=L(f(r1)*)RE的定义=L(f(r1*))RE的正则代换的定义=L(f(r))5.2RL的封闭性•例5-5设∑={0，1，2}，Δ={a，b}，正则代换f定义为：f(0)=ab；f(1)=b*a*；f(2)=a*(a+b)则：⑴f(00)=abab；⑵f(010)=abb*a*ab=ab+a+b；5.2RL的封闭性⑶f((0+1+2)*)=(ab+b*a*+a*(a+b))*=(b*a*+a*(a+b))*=(a+b)*；⑷f(0(0+1+2)*)=ab(ab+b*a*+a*(a+b))*=ab(a+b)*；⑸f(012)=abb*a*a*(a+b)=ab+a*(a+b)；⑹f((0+1)*)=(ab+b*a*)*=(ab+b+a+b*a*)*=(a+b)*。5.2RL的封闭性•同态映射(homomorphism)设∑、Δ是两个字母表，*:ff为映射，如果对于x，y∈∑*，f(xy)=f(x)f(y)，则称f为从∑到Δ*的同态映射。5.2RL的封闭性•对于L∑*，L的同态像LxxfLf)()(对于wΔ*，w的同态原像是一个集合}&)(|{)(*1xwxfxwf对于LΔ*，L的同态原像是一个集合})(|{)(1LxfxLf5.2RL的封闭性•例5-6设∑={0，1}，Δ={a，b}，同态映射f定义为f(0)=aaf(1)=aba则：⑴f(01)=aaaba；⑵f((01)*)=(aaaba)*；⑶f-1(aab)=Φ；5.2RL的封闭性⑷f-1(aa)={0}；⑸f-1({aaa，aba，abaaaaa，abaaaaaa})={1，100}；⑹f-1((ab+ba)*a)={1}；⑺f(f-1((ab+ba)*a))=f({1})={aba}。令L=(ab+ba)*a，上述(7)表明，f