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

形式语言与自动机理论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第8章CFL的性质•本章讨论CFL的性质•主要内容–CFL的泵引理及其应用、Ogden引理。–CFL的封闭性•封闭运算：并、乘、闭包、代换、同态映射、逆同态映射•不封闭运算：交、补第8章上下文无关语言的性质•CFL的判定算法。–判定CFG产生的语言是否为空、有穷、无穷。–一个给定的符号串是否为该文法产生的语言的一个句子等问题。•重点–CFL的封闭性、CFL的泵引理。•难点–CFL的泵引理的应用、CFL的同态原象是CFL。8.1上下文无关语言的泵引理•启发•RGG=(V，T，P，S)，使得L(G)=L，当x足够长时，如|x|≥|V|+1时，存在u、v、w∈T*，|v|≥1，使得x=uvw，当G为右线性文法时，必定存在语法变量A，使得如下派生成立：•S*uA*uvA*……*uviA*uviw•V是可以被重复任意多次的字串！•CFL也有类似性质？8.1上下文无关语言的泵引理•CFL的自嵌套特性：如果L是一个CFL，CFGG=(V，T，P，S)是产生L的文法。当L是一个无穷语言时，必存在w∈L，A∈V，α，β∈(V∪T)*，且α和β中至少有一个不为ε，使得如下派生成立S*γAδ+γαAβδ+z•文法G中存在有如下形式的派生A+αAβ8.1上下文无关语言的泵引理•这种类型的派生预示着•S*γAδ+γαAβδ+z•并且•S*γAδ+γαnAβnδ+z′•设α*v，β*x，γ*u，A*w，δ*y•可以得到如下派生8.1上下文无关语言的泵引理S*γAδ*uαAβδ*uαAβy…*uαnAβny*uvnAxny*uvnwxny8.1上下文无关语言的泵引理引理8-1（CFL的泵引理）对于任意的CFLL，存在仅仅依赖于L的正整数N，对于任意的z∈L，当|z|≥N时，存在u，v，w，x，y，使得z=uvwxy，同时满足：(1)|vwx|≤N；(2)|vx|≥1；(3)对于任意的非负整数i，uviwxiy∈L。8.1上下文无关语言的泵引理8.1上下文无关语言的泵引理•证明要点：（1）用CNF作为CFL的描述工具。（2）对于任意的z∈L，当k是z的语法树的最大路长时，必有|z|≤2k-1成立。（3）仅当z的语法树呈图8-1所示的满二元树时，才有|z|=2k-1，其他时候均有|z|2k-1。（4）取N=2|V|=2|V|+1-1，z∈L，|z|≥N。8.1上下文无关语言的泵引理8.1上下文无关语言的泵引理（5）取z的语法树中的最长的一条路p，p中的非叶子结点中必定有不同的结点标有相同的语法变量。（6）p中最接近叶子且都标有相同的语法变量A的两个结点为v1、v2，如图8-2所示。8.1上下文无关语言的泵引理•结点v1左边的所有叶子结点的标记从左到右构成的字符串为u；•结点v1的为根的子树中，v2左边的所有叶子结点的标记从左到右构成的字符串为v；•结点v2为根的子树的结果为w；•结点v1为根的子树中v2右边的所有叶子结点的标记从左到右构成的字符串为x；•结点v1右边的所有叶子结点的标记从左到右构成的字符串为y。8.1上下文无关语言的泵引理•z=uvwxy•注意到v1-子树的最大路长小于等于|V|+1，所以，v1的结果vwx满足：|vwx|≤2(|V|+1)-1=2|V|=N•v1的后代v2标记为变量A，所以，|vx|≥1。•此时有•S*uAy+uvAxy+uvwxy•显然，对于i=0，1，2，3，…•A*viAxi+viwxi8.1上下文无关语言的泵引理•总结上述推导（7）S*uAy+uvAxy+uvwxy=z，|vwx|≤2(|V|+1)-1=2|V|=N，|vx|≥1。（8）对于任意非负整数i，S*uAy+uviAxiy+uviwxiy。8.1上下文无关语言的泵引理•例8-1证明L={anbncn|n≥1}不是CFL。证明：取z=aNbNcN∈L⑴v=ah，x=bf，h+f≥1。•uviwxiy=aN+(i-1)hbN+(i-1)fcN，–当i≠1时，N+(i-1)h≠N和N+(i-1)f≠N中至少有一个成立。–uviwxiy=aN+(i-1)hbN+(i-1)fcNL。8.1上下文无关语言的泵引理⑵v=bh，x=cf，h+f≥1。•uviwxiy=aNbN+(i-1)hcN+(i-1)f–当i≠1时，N+(i-1)h≠N和N+(i-1)f≠N中至少有一个成立。–uviwxiy=aNhbN+(i-1)cN+(i-1)fL。•这些都与泵引理矛盾，所以，L不是CFL。8.1上下文无关语言的泵引理•例8-2证明L={anbmcndm|n，m≥1}不是CFL。证明：取z=aNbNcNdNv=ah、x=bf；v=bh、x=cf；v=ch、x=df，h+f≥1等4种情况。8.1上下文无关语言的泵引理•设v=ah、x=bf，并且h+f≥1•uviwxiy=aN+(i-1)hbN+(i-1)fcNdN•当i≠1时，N+(i-1)h≠N和N+(i-1)f≠N至少有一个成立。•uviwxiy=aN+(i-1)hbN+(i-1)fcNdNL8.1上下文无关语言的泵引理•同理可以证明，当v=bh、x=cf或者v=ch、x=df，h+f≥1时，uviwxiy=aN+(i-1)hbN+(i-1)fcNdNL对i≠1成立。•由泵引理，L不是CFL。8.1上下文无关语言的泵引理•L={anbmck|n≠m，m≠k，k≠n}是CFL么？•取z=aNbN+ncN+m其中，n≠m，n≠0，m≠0。•只能让v或者x由若干个a组成，才有可能随着i的变化，使得uviwxiy中a的个数与b的个数或者c的个数相同。•当v=ak，x=bh（N≥k≥1），显然，只要令k=h，就能保证对于任意的i，uviwxiy中字符a的个数永远不能等于字符b的个数。•希望uviwxiy中字符a的个数等于字符c的个数。8.1上下文无关语言的泵引理•想办法保证在N≥k≥1的条件下，总能找到一个i，使得uviwxiy中字符a的个数能够等于c的个数。•在uviwxiy中，字符a的个数为N+(i-1)k，而c的个数为N+m，即：N+(i-1)k=N+m。•从而要求，无论k取N到1的任何一个值，i=m/k+1必须是一个整数。8.1上下文无关语言的泵引理•取z=aNbN+N!cN+2N!•v=ak，x=bh，N≥k≥1•当i=2N!/k+1时，有uviwxiy=aN+(i-1)kbN+N!+(i-1)hcN+2N!=aN+(2N!/k+1-1)kbN+N!+(2N!/k+1-1)hcN+2N!=aN+(2N!/k)kbN+N!+(2N!/k)hcN+2N!=aN+2N!bN+N!+(2N!/k)hcN+2N!•uviwxiy=aN+2N!bN+N!+(2N!/k)hcN+2N!L。8.1上下文无关语言的泵引理•问题：当取v=bk，x=ch，N≥k≥1，时，我们就无法在找到矛盾了。•我们必须把目标锁定在a上！•因为这能保证找出“矛盾”！•所以我们实在是对a太“感兴趣”了！•称这些令我们感兴趣的字符为特异点(distinguishedposition)。8.1上下文无关语言的泵引理•？是否可以要求v和x中必须含有a。•这样必须修改原有的泵引理！•定义z的语法树满足下列条件的非叶子结点为分支点(branchpoint)：该结点有两个儿子，并且它的这两个儿子均有特异点后代。8.1上下文无关语言的泵引理引理8-2（Ogden引理）对于任意的CFLL，存在仅仅依赖于L的正整数N，对于任意的z∈L，当z中至少含有N个特异点时，存在u，v，w，x，y，使得z=uvwxy，同时满足:(1)|vwx|中特异点的个数≤N；(2)|vx|中特异点的个数≥1；(3)对于任意的非负整数i，uviwxiy∈L。8.1上下文无关语言的泵引理•证明要点：（1）与CFL的泵引理的证明类似。（2）用CNF作为CFL的描述工具。（3）取N=2|V|+1。（4）构造从树根到叶子的含有最多分支点的路径p。参考图8-2。8.1上下文无关语言的泵引理图8-2z的派生树8.1上下文无关语言的泵引理其中：•结点v1左边的所有叶子结点的标记从左到右构成的字符串为u；•结点v1的为根的子树中v2左边的所有叶子结点的标记从左到右构成的字符串为v；•结点v2为根的子树的结果为w；•结点v1的为根的子树中v2右边的所有叶子结点的标记从左到右构成的字符串为x；•结点v1右边的所有叶子结点的标记从左到右构成的字符串为y；8.1上下文无关语言的泵引理（5）p中至少有|V|+1个分支点，在这些分支结点中，至少有两个不同的结点标记有相同的变量A。（6）仍然参照图8-2，p中最接近叶子的且都标有相同的语法变量A的两个分支结点为v1、v2。（7）S*uAy+uvAxy+uvwxy=z。vwx中最多有N个特异点，vx至少有1个特异点。（8）对于任意的非负整数i，S*uAy+uviAxiy+uviwxiy。8.1上下文无关语言的泵引理•例8-3证明L={anbmchdj|n=0或者m=h=j}不是CFL。取z=abNcNdN⑴v=a，x=bk，k≠0此时uv2wx2y=aabN+kcNdNL；⑵v=bk，x=cg，k≠0，g≠0此时uv2wx2y=abN+kcN+gdNL；⑶v=bk，x=dg，k≠0，g≠0此时uv2wx2y=aabN+kcNdN+gL；与Ogden引理矛盾，所以，L不是CFL。8.2CFL的封闭性定理8-1CFL在并、乘积、闭包运算下是封闭的。证明要点：令CFG–G1=(V1，T1，P1，S1)，L(G1)=L1，–G2=(V2，T2，P2，S2)，L(G2)=L2，–V1∩V2=Φ，且S3，S4，S5V1∪V2。8.2CFL的封闭性G3=(V1∪V2∪{S3},T1∪T2,P1∪P2∪{S3S1|S2},S3)G4=(V1∪V2∪{S4},T1∪T2,P1∪P2∪{S4S1S2},S4)G5=(V1∪{S5}，T1，P1∪{S5S1S5|ε}，S5)显然，G3、G4、G5都是CFG，并且L(G3)=L1∪L2L(G4)=L1L2L(G5)=L1*8.2CFL