形式语言与自动机期末复习题及答案_第1页
形式语言与自动机期末复习题及答案_第2页
形式语言与自动机期末复习题及答案_第3页
形式语言与自动机期末复习题及答案_第4页
形式语言与自动机期末复习题及答案_第5页
已阅读5页,还剩2页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

[q12AC][q12AC]形式语言与自动机期末复习题及答案1.有图灵机M=(Q,E,r,5,q,B,F)接受语言何士亚底£缶4}*},按照下图说明其接受过程。(本题15分0)"] ["日二R L[q,B][q3,c]答:abtab的分析过程:[q1,B]abtab卜a[q°,a]btab卜ab[q°,a]tab卜abt[q°,a]ab1 V2 V2 V3卜ab[q,,B]tab卜a[q「,B]btabHq「,B]abtabV4VV5V6VV卜a[q,,B]btab卜ab[q°,b]tab卜abt[q°,b]abV1VVV2VVV3V卜abta[q0,b]b卜abt[q,,B]ab卜a[qr,B]btabVV V3VV 4 VV V5 VVVHab[qv,B]tab卜abt[q°,B]ab卜abta[q0,B]bVV 7VVVV 8 VV VVV 8VHabtab[qo,B]BHabta[q..,B]bVVVV8VVV9V接受abtab.简述《形式语言与自动机》课程的主要内容(本。题10分)答:语言的文法描述;RL(RG、FA、RE、RL的性质);CFL(CFG(CNF、GNF)、PDA、CFL的性质);TM(基本TM、构造技术、TM的修改);CSL(CSG、LBA)。.简述《形式语言与自动机》课程的学习目的和基本要求。(本题10分)答:本专业人员4种基本的专业能力:计算思维能力、算法的设计与分析能力、程序设计和实现能力、计算机软硬件系统的认知、分析、设计与应用能力。其中计算思维能力包括:逻辑思维能力和抽象思维能力、构造模型对问题进行形式化描述、理解和处理形式模型。本课程应使学生掌握如下知识:正则语言、下文无关语言的文法、识别模型及其基本性质、图灵机的基本知识。锻炼培养如下能力:形式化描述和抽象思维能力、了解和初步掌握“问题、形式化描述、自动化(计算机化)”这一最典型的计算机问题求解思路。4.利用下图说明CFL泵引理的原理(物理意义)。(本题15分)用CNF作为CFL的描述工具。对于任意的z£L,当k是z的语法树的最大路长时,必有|z|W2k-1成立。仅当z的语法树为满二叉树时,才有|z|=2k-1,其他时候均有|z|<2k-1。(3)取N=2|k|=2|k|+1-1。(4)取z的语法树中的最长的一条路k,k中的非叶子结点中必定有不同的结点标有相同的语法变量。(5)S0*uAy0+uvAxy0+uvwxyqz|vwxg2(|k|+1)-1=N|vx|三1(6)对于任意非负整数S0*uAy0+uvAxiy0+uvwxiy。.按照文法的乔姆斯基体系,文法被分为几类?各有什么样的特点?(本题10分)答:文法G=(V,T,P,S),其中V为变量的非空有穷集,T为终极符的非空有穷集,VHT=①,S£V,为文法G的开始符号,P为产生式的非空有穷集合。P中的元素均具有形式a—B,其中a£(VUT)+,且a中至少有V中元素的一个出现,B£(VUT)*。0型文法:文法G=(V,T,P,S)叫做0型文法或短语结构文法。L(G)叫做0型语言。也可以叫做短语结构语言。识别系统为TM。1型文法:G是0型文法并且对于VafB£P,均有|BlN|a|成立,也叫上下文有关文法。L(G)叫做1型语言或者上下文有关语言。识别系统为LBA。2型文法:G是1型文法并且对于Va—B£P,均有IBlNlal,并且a£V成立也叫上下文无关文法。L(G)叫做2型语言或者上下文无关语言。识别系统为PDA。3型文法:G是2型文法并且对于Va—B£P,a—B均具有形式A—w或A—wB其中A,BEV,wGT+oL(G)叫做3型语言。识别系统为FA。.设文法G的产生式集如下,试给出句子000111222的至少两个不同的推导和至少两个不同的归约 (本题10分)Sf0BC|0SBC0Bf011Bf11CBTC1Cf122Cf22推导一:S=>0SBC=>00SBCBC=>000BCBCBC=>0001CBCBC=>0001BCCBC=>00011CCBC=>00011CBCC=>00011BCCC=>000111CCC=>0001112CC=>000111222推导二:S=>0SBC=>00SBCBC=>000BCBCBC=>000BBCCBC=>000BBCBCC=>000BBBCCC=>0001BBCCC=>00011BCCC=>000111CCC=>0001112CC=>00011122C=>000111222归约一、归约二分别为推导一和推导二的逆过程.证明L={anbncn|nN1}不是CFL(这个要配合泵引理看)证明:利用反证法,假定L是CFL,N为泵引理所说的正整数,取z=aNbNcNEL,并且有|aNbNcN|=3N。证不存在u,v,w,x,yz=uvwxy,使得对于i=0,1,2,3,…,uviwxiyEL。也就是说,对于u,v,w,x,y的任意取法,都能找到一个特殊的i,使得uviwxiyEL。注意到影响uviwxiy是否为L的句子的因素是v和x,而u,w,y对uviwxiy来说是不变的,所以,证明将集中精力考察v和x的不同取法。再注意到IvwxIWN,所以v,w和x并在一起不能同时有3种字符,也就是说,v和x不能同时分别为a和c组成的串。当然,也不可以取它们为形如ahbf(h,f三1)的串,因为此时有uv2wx2yEL恒成立。所以,还有如下两种情况需要讨论:v=ah,x=bf,h+f三1。止匕时有uviwxiy=aN+(i)hbN+(i)/cn。当i/1时,N+(i-1)h/N和N+(i-1)f/N中至少有一个成立,所以,当i/1时,uviwxiy=aN+(i-1)hbN+(i-1)fCNEL。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中至少有一个成立,所以,当i/1时,uviwxiy=aNbN+(i-1)hcN+(i-1)fEL。所以,L不是CFL。.将下列语法转换成CNF:(本题15分)S—ASB|gA—0AS|0B—S1S|A|11a)因为A和B都产生终结符号,所以S也能产生终结符号,所以上述文法中没有无用符号。b)只有S产生式中含有£,所以将产生式右部中出现S的,用£替换后加到产生式中得到消除£一产生式的文法为:S->ASB|ABA->0AS|0A|0B->S1S|1S|S1|1|A|11c)单产生式是:B->A.因此,将A-产生式来代替A。结果是:S->ASB|ABA->0AS|0A|0和B->S1S|1S|S1|1|0AS|0A|0|11d)引入变量和产生式C->0和D->1,用C,D来代换非终结符中的0和1,得到结果:S->ASB|ABA->CAS|CA|0B->SDS|DS|SD|1|CAS|CA|0|DDC->0 D->1最后,分别用E,F,和G替换SB,AS,DS得到CNF文法:S->AE|ABA->CF|CA|0B->SG|DS|SD|1|CF|CA|0|DDC->0D->1E->SBF->ASG->DS.设已有CNF: ①AfBC ②BfCAIb③C^ABIa将其变换为GNF。(本题15分)解:⑴按其非终结符排列为A、B、C,A是低位,C是高位。⑵•・•①、②中,右部首符序号高于左部的非终结符,无需变换。对③,需要变换,将①代入③得:CfBCBIa④仍需变换,将②代入④得:CfCACBIbCBIa⑤⑶对上述变换后所得结果消直接左递归,对CfCACBIbCBIa变换为CfbCBIaIbCBC’IaC'⑥C,fACBIACBC, ⑦

⑷回代:将C的生成式⑥回代入B的生成式②B-CA|b被变换为:B-bCBAIaAIbCBC'AIaC'AIb⑧将新的B生成式⑧回代入A的生成式①A-BC被变换为:A-bCBACIaACIbCBC'ACIaC'ACIbC⑨再将新的A生成式⑨代入新引入的C'生成式⑦C’-ACBIACBC’被变换为C’-bCBACCBIaACCBIbCBC’ACCBIaC’ACCBIbCCBIbCBACCBC'IaACCBC'IbCBC'ACCBC'IaC'ACCBC'IbCCBC’⑩GNF中的产生式为:⑨、⑧、⑥、⑩10.正则语言有5种等价的描述模型:正则文法(RG)、确定的有穷状态自动机(DFA)、不确定的有穷状态自动机(脂八)、带空移动的有穷状态自动机(£-NFA)、正则表达式(RE)。这5种等价模型的转换关系可以用下图表示:整理这些不同模型间等价证明的思路。(本题25分)(1)DFAnRGRG分为右线性文法和左线性文法。对于右线性文法,只需要采用模拟M的移动即可P={q-ap15(q,a)=p}|J{q—a18(q,a)=p,pgF},M的开始符号就是G的开始符号。而对于左线性文法,G用规约模拟M的移动:P={p-qa।5(q,a)=p}U{Zfqa15(q,a)=p,pgF}U{pfa।5(q°,a)=p}新增加的符号Z为G的识别符号,也就是开始符号。(2)RGnNFA同上,分为右线性和左线性文法。对于右线性文法:{B|A—aBgP}U{Z}如果A—agP5(A,a)<{B|A—aBgP}如果5(A,a)<其中,G的开始符号为M的开始符号,新增的状态Z为M的终止状态。对于左线性文法:增加Z为M的开始状态;对应形如Afa的产生式,定义Ag5(Z,a);对应形如AfBa的产生式,定义Ag8(B,a);G的开始符号为M的终止状态。(3)(4)(5)DFAnRE采用图上作业法:预处理、并弧、去状态、处理:REn£-NFA由于NFA也是一个特殊的£-NFA,则其转化可以参考RGnNFA£-NFAnNFAFNFA£-NFA£-NFAu{狐}如果尸n£—CLOSURE。中Q如果FHe-CLOSURE。=QNFAnDFA:确定化(6)画图的解法:11.设计PDA接受下列语言(注意:不要求为确定的){0m1nImWn};(本题15分)设PDAM=(Q,T,r,6,q0,Z0,F),其中:r={0,1,Z0},F={qf},6定义如下:6(q0,£,Z0)={(q1,Z0)},6(q0,0,0)={(q0,00)},6(q0,1,0)={(q1,£

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论