形式语言与自动机课后习题答案 第二章 4．找出右线性文法，能构成长度为1至5个字符且以字母为首的字符串。 答：G={N,T,P,S} 其中N={S,A,B,C,D} T={x,y} 其中x ∈{所有字母} y ∈{所有的字符} P 如下: S →x S →xA A →y A →yB B →y B →y C C →y C →y D D →y 6．构造上下文无关文法能够产生 L={ω/ω∈{a,b}*且ω中a 的个数是b 的两倍} ! 答：G={N,T,P,S} 其中N={S} T={a,b} P 如下: S →aab S →aba S →baa S →aabS S →aaSb S →aSab S →Saab S →abaS S →abSa S →aSba S →Saba S →baaS S →baSa S →bSaa S →Sbaa 7．找出由下列各组生成式产生的语言（起始符为S ） (1) S →SaS S →b (2) S →aSb S →c (3) / (4) S →a S →aE E →aS 答：（1）b(ab)n /n ≥0}或者L={(ba)n b /n ≥0} (2) L={a n cb n /n ≥0} (3) L={a 2n+1 /n ≥0} 第三章 1． 下列集合是否为正则集，若是正则集写出其正则式。 （1） 含有偶数个a 和奇数个b 的{a,b}*上的字符串集合 （2） 含有相同个数a 和b 的字符串集合 （3） < （4） 不含子串aba 的{a,b}*上的字符串集合 答：（1）是正则集，自动机如下 a
a (2) 不是正则集，用泵浦引理可以证明，具体见17题（2）。 (3) 是正则集 先看L’为包含子串aba的{a,b}*上的字符串集合 { 显然这是正则集，可以写出表达式和画出自动机。（略）则不包含子串aba的{a,b}*上的字符串集合L是L’的非。 根据正则集的性质，L也是正则集。 4．对下列文法的生成式，找出其正则式 （1）G=({S,A,B,C,D},{a,b,c,d},P,S),生成式P如下： S→aA S→B A→abS A→bB B→b B→cC C→D D→bB … D→d （2）G=({S,A,B,C,D},{a,b,c,d},P,S),生成式P如下： S→aA S→B A→cC A→bB B→bB B→a C→D C→abB D→d 答：(1) 由生成式得： S=aA+B ① A=abS+bB ② ] B=b+cC ③ C=D ④ D=d+bB ⑤ ③④⑤式化简消去CD，得到B=b+c(d+bB) 即B=cbB+cd+b =>B=(cb)*(cd+b) ⑥ 将②⑥代入① S=aabS+ab(cb)*(cd+b)+(cb)*(cd+b) =>S=(aab)*(ab+ε)(cb)*(cd+b) (2) 由生成式得： S=aA+B ① A=bB+cC ② … B=a+bB ③ C=D+abB ④ D=dB ⑤ 由③得B=b*a ⑥
（英语）英语翻译专项习题及答案解析含解析 一、高中英语翻译 1．高中英语翻译题：Translate the following sentences into English, using the words given in the brackets. 1．美食是人们造访上海的乐趣之一。（visit） 2．街头艺术家运用创意将鲜艳明亮的色彩带进了老社区。（bring） 3．在你生命中，如果有一个人你需要对他说对不起，那么就去向他道歉吧。（apology）4．这个游戏的独特之处在于它让孩子学会如何应对现实生活中的问题。（what） 5．申请材料需要精心准备，这样你心仪的学校才会对你的能力有全面、准确地了解。（in order that） 【答案】 1．Delicious food is one of the pleasures when people visit Shanghai. 2．Street artists bring bright and vivid colors into older neighborhoods with originality 3．If there is someone to whom you need say sorry in your life, make an apology to him. 4．What makes this game peculiar lies in that it teaches kids how to handle the problems in real life. 5．The applications should be carefully prepared in order that the school you like can have an overall and accurate knowledge of your abilities. 【解析】 【分析】 1．本句重点考察两个知识点。一个是乐趣之一，说明此处的乐趣应该用复数，必须是可数名词，因此选择pleasure。另一个是题目中给出的visit，需要谨慎处理，是用做动词还是名词。此处我们给出一个时间状语从句when people visit Shanghai，同时还可使用其他从句进行处理。所以答案是Delicious food is one of the pleasures when people visit Shanghai. 2．本题难度不大，重点是明亮的色彩的表达，可以使用bright colors, 也可以使用bright and vivid colors. 所以答案是Street artists bring bright and vivid colors into older neighborhoods with originality 3．本题考查there be + 定语从句从而构成条件状语从句。另外考察“道歉”用“make apology to sb.”。所以答案是If there is someone to whom you need say sorry in your life, make an apology to him. 4．本题考察what引导的主语从句，以及“be peculiar to”的用法。所以答案是What makes this game peculiar lies in that it teaches kids how to handle the problems in real life. 5．本题主要考固定词组的掌握，为了使用in order that引导出的目的状语从句。另外也考查 preferred school，have…knowledge/ understanding of…，overall，accurate等。所以答案是The applications should be carefully prepared in order that the school you like can have an overall and accurate knowledge of your abilities. 【考点定位】翻译句子
形式语言与自动机理论试题答案解析 一、按要求完成下列填空 1.给出集合{Φ,{Φ}}和集合{ε,0,00}的幂集（2x4'） (1) {Φ,{Φ},{{Φ}},{Φ,{Φ}}} (2) {Φ,{ε},{0},{00},{ε,0},{ε,00},{0,00},{ε,0,00}} 2.设∑={0,1},请给出∑上的下列语言的文法（2x5'） (1)所有包含子串01011的串 S→X01011Y X→ε|0X|1X Y→ε|0Y|1Y (2)所有既没有一对连续的0，也没有一对连续的1的串 A→ε|A’|A” A’→0|01|01A’ A”→1|10|10A” 3.构造识别下列语言的DFA 2x6' (1) {x|x∈{0，1}+且x以0开头以1结尾} （设置陷阱状态，当第一个字符为1时，进入陷阱状态） (2) {x|x∈{0，1}+且x的第十个字符为1} （设置一个陷阱状态，一旦发现x的第十个字符为0，进入陷阱状态）
二、判断（正确的写T ，错误的写F ） 5x2' 1.设1R 和2R 是集合{a,b,c,d,e}上的二元关系，则 3231321)(R R R R R R R I I ? ( T ) 任取(x.,y),其中x,y },,,,{e d c b a ∈，使得321)(),(R R R y x I ∈。 )),(),((321R y z R R z x z ∈∧∈??I },,,,{e d c b a z ∈ )),(),(),((321R y z R z x R z x z ∈∧∈∧∈?? )),(),(()),(),((3231R y z R z x z R y z R z x z ∈∧∈?∧∈∧∈?? 3231),(),(R R y x R R y x ∈∧∈? 3231),(R R R R y x I ∈? 2.对于任一非空集合A ，Φ?A 2 ( T ) 3.文法G ：S A|AS A a|b|c|d|e|f|g 是RG ( F ) 4.3型语言 I 2型语言 I 1型语言 I 0型语言 ( F ) 5.s （rs+s ）*r=rr *s （rr *s ）* ( F ) 不成立，假设r,s 分别是表示语言R ，S 的正则表达式，例如当R={0}，S={1}, L(s(rs+s)*r)是以1开头的字符串，而L(rr*s(rr*s)*)是以0开头的字符串.L(s(rs+s)*r) ≠ L(rr*s(rr*s)*) 所以s(rs+s)*r ≠ rr*s(rr*s)*,结论不成立 三、设文法G 的产生式集如下，试给出句子aaabbbccc 的至少两个不同的推导（12分）。 aSBC aBC S |→ ab aB → bB →bb CB →BC bC →bc cC →cc
编译原理作业三 T3-1构造自动机A ，使得它能识别形式如±dd*·d*E ±dd 的实数，其中，d ∈{0,1,2,3,4,5,6,7,8,9} T3-4将图所示NFA 确定化和最小化。 解：依据该NFSA 的状态图构造DFSA 如下表所示。 I I x I y [q 0] 0 [q 1] 1 [q 2] 2 [q 1] 1 [q 2,q 3] 3 [q 2] 2 [q 1,q 3] 4 [q 2,q 3] 3 [q 3,q 4] 5 [q 1,q 3] 4 [q 1,q 3] 4 [q 2,q 3,q 4] 6 [q 3] 7 [q 3,q 4] 5 [q 3,q 4] 5 [q 3] 7 [q 2,q 3,q 4] 6 [q 3,q 4] 5 [q 1,q 3] 4 [q 3] 7 [q 3,q 4] 5 [q 3] 7 DFSA 相应的状态图如下图所示： 6 1 2 3 4 5 7 X X y y y X X X X X y y y y S 3 1 4 2 5 6 7 ± d E d d d d ±
对DFSA 进行最小化： 已知K={0，1,2,3,4,5,6,7}，K 可分为两个子集 K1={0,1,2,3,4,7}（非终态集） K2={5,6}（终态集） 在K1中，因为状态1只有x 输入，状态2只有y 输入，其他状态均有x ，y 输入，所以可以将K1分割为K11={0,3,4,7} K12={1} K13={2} 在K11中 {0}x=1∈K12 {3,4,7}x={5,6}?K2 故可将K11分割为 K111={0} K111={3,4,7} {3,4,7}x={5,6}?K2 {3,4,7}y={4,7}?K111 因此状态3,4,7是否等价取决于对K2的划分结果 在状态K2={5,6}中 {5,6}x=5∈K2 {5,6}y={4,7}?K111 所以状态5,6等价，所以状态3,4,7等价 所以，将原状态集合划分为{0}、{3,4,7}、{1}、{2}、{5,6} 最小化后的状态图为： S 1 2 3 5 X X X X y y y y
形式语言与自动机的发展和在计算理论中的作用 2015060104020王桢 形式语言是语言学衍生过来的，开始形式语言并没有用于研究计算机编程语言，而只是研究自然语言的结构。在电子计算机出现以后，人们就马上想到用计算机来作自然语言的机械翻译。可是这项工作并没有所成果，对自然语言的结构 理解太片面化，翻译质量不理想也很难提高。1956年，乔姆斯基发表了用形 式语言方法研究自然语言的第一篇文章。他对语言进行定义：给定一组符号，称 为字母表，用∑表示。又用∑*表示∑中字母组成的所有符号串的集合。∑*的每个子集都是∑上的一个语言。乔姆斯基的语言定义方法为人们所公认，一直沿用下来，乔姆斯基根据文法将语言分成3大类。同时克林在研究神经细跑中，建立 了识别语言的系统有穷状态自动机。乔姆斯基发现自动机和文法分别从生成和识别去表达语言，并建立了形式文法和自动机之间的联系，证明语言的形式文法与自动机之间存在着如下的对应关系：①若某一语言能用图灵机来识别，则它就能 用O型文法生成，反之亦然；②若某一语言能用线性有界自动机来识别，则它 就能用上下文敏感文法生成，反之亦然；③若某一语言能用后进先出自动机来识别，则它就能用上下文自由文法生成，反之亦然；④若某一语言能用有限自动机来识别，则它就能用有限状态文法生成，反之亦然。这一成果将形式语言引入数 学，使得形式语言真正诞生。1960年，算法语言ALGOL60报告发表。1961年，又发表了ALGOL60修改报告。在这两个报告中，第一次使用一种称为BNF 范式的形式方法来描述程序设计语言ALGOL60的语法。不久，人们即发现BNF 范式极其类似于形式语言理论中的上下文无关文法，从而打开了形式语言广泛应用于程序设计语言的局面，并给形式语言理论本身的研究以极大的推动，使它发展成为理论计算机科学的一个重要分支。 形式语言理论是从语言学衍生而来，作为一种理解自然语言的句法规律。在发展过程中人们发现其在计算机语言中的作用，计算机语言在计算机科学中，形式语言通常作为定义编程语言和语法的基础。对编程语言编译，使之转换成机器语言，形式语言在这一工作中有很重要的作用。形式语言推动了计算机学科的发展，并成为计算机学科里重要的分支。 19世纪中，布尔用数学方法研究思维规律的问题建立了逻辑代数，即布尔代数。肖斯塔科夫和仙农，独立地应用布尔代数于继电器接点电路的分析和综合,
汉译英专项练习 一、倍数增减的表示法 5 1) Force N1 _______________(比力N2大2.5倍). is 2.5 times greater than Force N2 （考点：倍数+形容词/副词比较级+ than） 2) This substance _______________(反应速度是另外那种物质的三倍). reacts three times as fast as the other one （考点：倍数+ as +形容词/副词+ as） 3) The earth _______________(是月球大小的49倍). is 49 times the size of the moon （考点：倍数+名词） 4) The landlord _______________(想将租金提高三分之一). wants to raise the rent by a third （考点：动词+ by +数词/百分比/倍数） 5) They _______________(计划将投资增加一倍). plan to double their investment （考点：double +名词） 二、时态6 1) Be quick, _______________(否则等我们到达教堂时婚礼就已经结束了). or the wedding will have finished by the time we get to the church （考点：将来完成时） 2) When she got home, _______________(孩子们已经睡着了). the children had fallen asleep （考点：过去完成时） 3) When I prepare for the college entrance examination, _______________(我姐姐将在海边度假). my sister will be taking her vacation at the seaside （考点：将来进行时） 4) I_______________(一上午都在修改我的简历). have been revising my resume all the morning （考点：现在完成进行时） 5) Do you often go on holiday? _______________(不，我已经有五年没有度假了). No. It has been five years since I went on holiday （考点：It has been…since sb. did sth.表示某人有多长时间没有做某事了） 6) He joined the army in October, 2001. _______________(他参军已五年了). He has been in the army for 5 years （考点：1.现在完成时；2.要用持续性动词才能接一段时间） 三、被动语态5 1) The blackboard and chalk _______________(正在被电脑和投影机所取代). is being replaced by the computer and the projector （考点：被动语态的现在进行时） 2) The book _______________(到今年年底就将已出版). will have been published by the end of this year （考点：被动语态的将来完成时）
第三章作业答案 1．已知DFA M1与M2如图3－18所示。 (敖雪峰 02282068) (1) 请分别给出它们在处理字符串1011001的过程中经过的状态序列。 (2) 请给出它们的形式描述。 S q q 1 图3－18 两个不同的DFA 解答：(1)M1在处理1011001的过程中经过的状态序列为q 0q 3q 1q 3q 2q 3q 1q 3; M2在处理1011001的过程中经过的状态序列为q 0q 2q 3q 1q 3q 2q 3q 1; (2)考虑到用形式语言表示,用自然语言似乎不是那么容易,所以用图上作业法把它们用正则表达式来描述: M1: [01+(00+1)(11+0)][11+(10+0)(11+0)]* M2: (01+1+000){(01)*+[(001+11)(01+1+000)]*} ******************************************************************************* 2．构造下列语言的DFA ( 陶文婧 02282085 ) （1）{0，1}* ，1 （2）{0 ，1}+ ，1 （3）{x|x {0，1}+且x 中不含00的串} （设置一个陷阱状态，一旦发现有00的子串，就进入陷阱状态）
（4）{ x|x∈{0，1}*且x中不含00的串} （可接受空字符串，所以初始状态也是接受状态） （5）{x|x∈{0，1}+且x中含形如10110的子串} （6）{x|x∈{0，1}+且x中不含形如10110的子串} （设置一个陷阱状态，一旦发现有00的子串，就进入陷阱状态） （7）{x|x∈{0，1}+且当把x看成二进制时，x模5和3同余，要求当x为0时，|x|=1,且x≠0时，x的首字符为1 } 1.以0开头的串不被接受，故设置陷阱状态，当DFA在启动状态读入的符号为0，则进 入陷阱状态 2.设置7个状态：开始状态q s,q0:除以5余0的等价类，q1：除以5余1的等价类,q2:除以5 余2的等价类，q3:除以5余3的等价类，q4:除以5余4的等价类，接受状态q t
第三章 ******************************************************* ************************ 1．构造下列语言的DFA ( 陶文婧 02282085 ) （1）{0，1}* ，1 （2）{0，1}+ ，1 （3）{x|x{0，1}+且x中不含00的串} （设置一个陷阱状态，一旦发现有00的子串，就进入陷阱状态） （4）{ x|x{0，1}*且x中不含00的串} （可接受空字符串，所以初始状态也是接受状态） （5）{x|x{0，1}+且x中含形如10110的子串} （6）{x|x{0，1}+且x中不含形如10110的子串} （设置一个陷阱状态，一旦发现有00的子串，就进入陷阱状态）
（7）{x|x{0，1}+且当把x看成二进制时，x模5和3同余，要求当x为0时，|x|=1,且x0时，x的首字符为1 } 1.以0开头的串不被接受，故设置陷阱状态，当DFA在启动状态读入的符号为0，则进 入陷阱状态 2.设置7个状态：开始状态q s,q0:除以5余0的等价类，q1：除以5余1的等价类,q2:除以5 余2的等价类，q3:除以5余3的等价类，q4:除以5余4的等价类，接受状态q t （8）{x|x{0，1}+且x的第十个字符为1} （设置一个陷阱状态，一旦发现x的第十个字符为0，进入陷阱状态） （9）{x|x{0，1}+且x以0开头以1结尾} （设置陷阱状态，当第一个字符为1时，进入陷阱状态）
（10）{x|x{0，1}+且x中至少含有两个1} （11）{x|x {0，1}+且如果x以1结尾，则它的长度为偶数；如果x以0结尾，则它的长度为奇数} 可将{0，1}+的字符串分为4个等价类。 q0：[]的等价类，对应的状态为终止状态 q1:x的长度为奇且以0结尾的等价类 q2：x的长度为奇且以1结尾的等价类 q3: x的长度为偶且以0结尾的等价类 q4: x的长度为偶且以1结尾的等价类 （12）{x|x是十进制非负数}
1)你应该适当花一点时间休息和锻炼。(reasonable) You should spend a reasonable amount of time relaxing and exercising. 2) 总的来说，孩子们比过去任何时候都更健康，受到了更好的教育。(in general) In general, children are healthier and better educated than ever before. 3) 待适当的机会来临，他就能抓住。(come along) Wh en the right opportunity comes along, he’ll take it. 4）每天他都留出点时间跟家人在一起，享受生活。(set aside) Every day he sets aside some time to be with his family and enjoy life 5) 我记得那些黑暗的街道以及同父亲手拉手走路的情景。(hand in hand) I remember those dark streets and walking hand in hand with my father 6) 他最终辜负了父母的期望。(live up to) He finally failed to live up to his parents’ expectations. 相比之下，我们的用油量大幅度上升了。(in contrast) In contrast, our use of oil has increased enormously. 8) 经过努力，他成功地克服了自己的致命弱点。(overcome) He succeeded in his efforts to overcome his fatal weakness. 1) 人们认为，悲观常常会导致绝望、疾病和失败。 It is believed that pessimism often leads to hopelessness, sickness and failure. 2) 与此相反，乐观主义能使你幸福、健康和成功。 Optimism, by contrast, can make you happy, healthy and successful. 3) 当你做某件事失败时，把失败当作一种学习的经历从中汲取益处。 When you fail in something, profit from the failure as a learning experience ) 在问题或困难面前，要想想自己的长处并树立起自信心。 Think about your strengths and build up self-confidence in front of problems or difficulties. 5) 不要让消极的想法阻碍你。 Don’t let negative thoughts hold y ou back. 6) 每个人都经历过失败和失望，因此不要过多地责怪自己。 Everyone has experienced failures and disappointments, so don’t blame yourself too much. 1) She wore a dress ____with a pattern of rose__________ (有玫瑰图案) on it. 2) Helen had ____prepared a wonderful/good meal for us_ (为我们准备了一顿丰盛的饭菜). 3) Ann _______promised faithfully___ (信誓旦旦地保证) that she would never tell. 4) Could you ____deliver this letter__ (把这封信送到) to the accounts department? 5) We were offered ____a selection of milk and plain____chocolate (精选的牛奶巧克力和纯巧克力). 6) Tell the children to ___keep out of mischief / behave themselves_____(别胡闹). 7) We could hear _____the sound of distant thunder_____ (远处打雷的声音). 8) The project has now __received approval from the government (得到政府的批准). 9) Kelly loved her husband ____in spite of the fact that he drank too much (虽然他喝酒太多). 10) Experts seem unable to ____agree whether the drug is safe or not_ (就这个药是否安全取得一致意见). 1. Not every bomb has hit its target. 并非每个炸弹都击中了目标。 2. We can have one or the other but not both simultaneously. 我们能够得到其中一个，但不能同时两个都有。 3. She wanted nothing more than work. 她只想要工作。 4. You cannot be too careful. 你越仔细越好。 5. I have yet to receive an apology from a child who just ran over my foot while chasing a sibling. 有个小孩在追逐自家的兄弟姐妹时踩了我的脚，却仍未向我道歉。 1. 并非所有父母都和你一样能提供很多情况。 Not all parents are as informative as you
形式语言与自动机课后作业答案 第二章 4．找出右线性文法，能构成长度为1至5个字符且以字母为首的字符串。 答：G={N,T,P,S} 其中N={S,A,B,C,D} T={x,y} 其中x∈{所有字母} y∈{所有的字符} P如下: S→x S→xA A→y A→yB B→y B→yC C→y C→yD D→y 6．构造上下文无关文法能够产生 L={ω/ω∈{a,b}*且ω中a的个数是b的两倍} 答：G={N,T,P,S} 其中N={S} T={a,b} P如下: S→aab S→aba S→baa S→aabS S→aaSb S→aSab S→Saab S→abaS S→abSa S→aSba S→Saba S→baaS S→baSa S→bSaa S→Sbaa 7．找出由下列各组生成式产生的语言（起始符为S） (1)S→SaS S→b (2)S→aSb S→c (3)S→a S→aE E→aS 答：（1）b(ab)n /n≥0}或者L={(ba)n b/n≥0} (2) L={a n cb n /n≥0} (3)L={a2n+1 /n≥0} 第三章 1．下列集合是否为正则集，若是正则集写出其正则式。 （1）含有偶数个a和奇数个b的{a,b}*上的字符串集合 （2）含有相同个数a和b的字符串集合 （3）不含子串aba的{a,b}*上的字符串集合 答：（1）是正则集，自动机如下 (2) 不是正则集，用泵浦引理可以证明，具体见17题（2）。
(3) 是正则集 先看L’为包含子串aba的{a,b}*上的字符串集合 显然这是正则集，可以写出表达式和画出自动机。（略） 则不包含子串aba的{a,b}*上的字符串集合L是L’的非。 根据正则集的性质，L也是正则集。 4．对下列文法的生成式，找出其正则式 （1）G=({S,A,B,C,D},{a,b,c,d},P,S),生成式P如下： S→aA S→B A→abS A→bB B→b B→cC C→D D→bB D→d （2）G=({S,A,B,C,D},{a,b,c,d},P,S),生成式P如下： S→aA S→B A→cC A→bB B→bB B→a C→D C→abB D→d 答：(1) 由生成式得： S=aA+B ① A=abS+bB ② B=b+cC ③ C=D ④ D=d+bB ⑤ ③④⑤式化简消去CD，得到B=b+c(d+bB) 即B=cbB+cd+b =>B=(cb)*(cd+b) ⑥ 将②⑥代入① S=aabS+ab(cb)*(cd+b)+(cb)*(cd+b) =>S=(aab)*(ab+ε)(cb)*(cd+b) (2) 由生成式得： S=aA+B ① A=bB+cC ② B=a+bB ③ C=D+abB ④ D=dB ⑤ 由③得 B=b*a ⑥ 将⑤⑥代入④ C=d+abb*a=d+ab+a ⑦ 将⑥⑦代入② A=b+a+c(d+b+a) ⑧ 将⑥⑧代入① S=a(b+a+c(d+ab+a))+b*a =ab+a+acd+acab+a+b*a 5.为下列正则集，构造右线性文法： (1){a,b}* (2)以abb结尾的由a和b组成的所有字符串的集合
第三章词法分析 本章要点 １．词法分析器设计， ２．正规表达式与有限自动机， ３．词法分析器自动生成。 本章目标： １．理解对词法分析器的任务，掌握词法分析器的设计； ２．掌握正规表达式与有限自动机； ３．掌握词法分析器的自动产生。 本章重点： 1．词法分析器的作用和接口，用高级语言编写词法分析器等内容，它们与词法分析器的实现有关。应重点掌握词法分析器的任务与设计，状态转换图等内容。 2．掌握下面涉及的一些概念，它们之间转换的技巧、方法或算法。 （1）非形式描述的语言?正规式 （2）正规式→ NFA（非确定的有限自动机） （3）NFA → DFA（确定的有限自动机） （4）DFA →最简DFA 本章难点 （1）非形式描述的语言?正规式 （2）正规式→ NFA（非确定的有限自动机） （3）NFA → DFA（确定的有限自动机） （4）DFA →最简DFA
作业题 一、单项选择题 （按照组卷方案，至少15道） 1. 程序语言下面的单词符号中，一般不需要超前搜索 a. 关键字 b. 标识符 c. 常数 d. 算符和界符 2. 在状态转换图的实现中，一般对应一个循环语句 a. 不含回路的分叉结点 b. 含回路的状态结点 c. 终态结点 d. 都不是 3. 用了表示字母，d表示数字， ={l，d}，则定义标识符的正则表达式可以是：。 (a)ld*(b)ll*(c)l(l | d)*(d)ll* | d* 4. 正规表达式(ε|a|b)2表示的集合是 (a){ε，ab，ba，aa，bb} (b){ab，ba，aa，bb} (c){a，b，ab，aa，ba，bb} (d){ε，a，b，aa，bb，ab，ba} 5. 有限状态自动机可用五元组（V T，Q，δ，q0，Q f）来描述，设有一有限状态自动机M的定义如下： V T={0，1}，Q={q0，q1，q2}，Q f={q2}，δ的定义为： δ（q0，0）=q1δ（q1，0）=q2 δ（q2，1）=q2δ（q2，0）=q2 M所对应的状态转换图为。
（英语）翻译练习题含答案及解析 一、高中英语翻译 1．高中英语翻译题：Translation: Translate the following sentences into English, using the words given in the brackets. 1．究竟是什么激发小王学习电子工程的积极性？(motivate) 2．网上支付方便了客户，但是牺牲了他们的隐私。(at the cost of) 3．让我的父母非常满意的是，从这个公寓的餐厅可以俯视街对面的世纪公园，从起居室也可以。(so) 4．博物馆疏于管理，展品积灰，门厅冷落，急需改善。(whose) 【答案】 1．What on earth has motivated Xiao Wang’s enthusiasm/ initiative to major in electronic engineering? 2．Online payment brings convenience to consumers at the cost of their privacy. 3．To my parents’ satisfaction, the d ining room of this apartment overlooks the Century Park opposite the street and so it is with the sitting room. 或者What makes my parents really satisfy is that they can see the Century Park from the dining room of this apartment, so can they from the living room. 4．This museum is not well managed, whose exhibits are covered with dust, and there are few visitors, so everything is badly in need of improvement. 或The museum whose management is reckless, whose exhibits are piled with dust and whose lobby is deserted, requires immediate improvement. 【解析】 1．motivate sb to do sth 激发某人做某事，on earth究竟，major in 以…为专业，enthusiasm/ initiative热情/积极性，故翻译为What on earth has motivated Xiao Wang’s enthusiasm/ initiative to major in electronic engineering? 2．online payment网上支付，brings convenience to给…带来方便，at the cost of以…为代价，privacy隐私，故翻译为Online payment brings convenience to consumers at the cost of their privacy. 3．To my parents’ satisfaction令我父母满意的是，后者也那样so it is with。也可以用主语从句What makes my parents really satisfy 表语从句thatthey can see the Century Park from the dining room of this apartment。overlooks俯视，opposite the street街对面，living room 起居室。故翻译为To my parents’ satisfaction, the dining room of this apartment overlooks the Century Park opposite the street and so it is with the sitting room.或者What makes my parents really satisfy is that they can see the Century Park from the dining room of this apartment, so can they from the living room. 4．not well managed/ management is reckless疏于管理，be covered with dust/ be piled with dust被灰尘覆盖，few visitors游客稀少，be badly in need of improvement/ requires immediate improvement亟需改善。故翻译为his museum is not well managed, whose exhibits
形式语言与自动机理论试题答案解析 一、按要求完成下列填空 1. 给出集合{Φ,{Φ}}和集合{ε,0,00}的幂集 （2x4'） (1) {Φ,{Φ},{{Φ}},{Φ,{Φ}}} (2) {Φ,{ε},{0},{00},{ε,0},{ε,00},{0,00},{ε,0,00}} 2. 设∑={0,1},请给出∑上的下列语言的文法 （2x5'） (1)所有包含子串01011的串 S →X01011Y X →ε|0X|1X Y →ε|0Y|1Y (2)所有既没有一对连续的0，也没有一对连续的1的串 A →ε |A ’|A ” A’ →0|01|01A ’ A ” →1|10|10A ” 3. 构造识别下列语言的DFA 2x6' (1) {x|x ∈{0，1}+且x 以0开头以1结尾} （设置陷阱状态，当第一个字符为1时，进入陷阱状态） 1 S 1 1 0,10 (2) {x|x ∈{0，1} + 且x 的第十个字符为1} （设置一个陷阱状态，一旦发现x 的第十个字符为0，进入陷阱状态） 1S 0,1 0,10,10,10,110,0,10,10,10,1 0,1
二、判断（正确的写T ，错误的写F ） 5x2' 1.设1R 和2R 是集合{a,b,c,d,e}上的二元关系，则 3231321)(R R R R R R R ? ( T ) 任取(x.,y),其中x,y },,,,{e d c b a ∈，使得321)(),(R R R y x ∈。 )),(),((321R y z R R z x z ∈∧∈?? },,,,{e d c b a z ∈ )),(),(),((321R y z R z x R z x z ∈∧∈∧∈?? )),(),(()),(),((3231R y z R z x z R y z R z x z ∈∧∈?∧∈∧∈?? 3231),(),(R R y x R R y x ∈∧∈? 3231),(R R R R y x ∈? 2.对于任一非空集合A ，Φ?A 2 ( T ) 3.文法G ：S A|AS A a|b|c|d|e|f|g 是RG ( F ) 4.3型语言 2型语言 1型语言 0型语言 ( F ) 5.s （rs+s ）*r=rr *s （rr *s ）* ( F ) 不成立，假设r,s 分别是表示语言R ，S 的正则表达式，例如当R={0}，S={1}, L(s(rs+s)*r)是以1开头的字符串，而L(rr*s(rr*s)*)是以0开头的字符串.L(s(rs+s)*r) ≠ L(rr*s(rr*s)*) 所以s(rs+s)*r ≠ rr*s(rr*s)*,结论不成立 三、设文法G 的产生式集如下，试给出句子aaabbbccc 的至少两个不同的推导（12分）。 aSBC aBC S |→ ab aB → bB →bb CB →BC bC →bc cC →cc
（英语）英语翻译专题练习(及答案) 一、高中英语翻译 1．高中英语翻译题：Translate tbe following sentences into English, using the words given in the brackets. 1．我们打篮球的时间到了。 (time) 2．他设法把游客及时送到了机场。 (manage) 3．你今晚能来参加我的生日聚会? (possible) 4．应该鼓励年轻人按照自己的特长选择职业。(encourage) 5．我对学生所谈的电子产品一无所知，我发现自己落伍了。(ignorant) 6．尽管遭受如重的自然灾害，但只要不灰心，我们终会克服暂时的困难。(Although...) 【答案】 1．It’s time for us to play basketball. 2．He managed to send the tourists to the airport in time. 3．Is it possible for you to attend my birthday party this evening? 4．Young people should be encouraged to choose their careers according to their own strong points. 5．Being ignorant of the electronic products the students are talking about, I find myself left behind. 6．Although we are suffering such a severe natural disaster, we will eventually overcome the temporary difficult as long as we don’t lose heart. 【解析】 1．考查time的用法。分析句子可知，本句为一般现在时，it is time for sb to do sth “该到某人做某事了”。为固定句型。再根据其它提示。故翻译为：It’s time for us to play basketball。2．考查manage的用法和一般过去时。分析句子可知，本句为一般过去时，manage to do sth“设法做某事”为固定短语。in time“ 及时”为介词短语，在句中作状语。再根据其它提示。故翻译为：He managed to send the tourists to the airport in time。 3．考查possible的用法和一般现在时。分析句子可知，本句为一般现在时，it is possible for sb to do sth “ 某人做某事是可能的”，it作为形式主语完成整个句子，不定式作为真正主语。再根据其它汉语提示。故翻译为：Is it possible for you to attend my birthday party this evening? 4．考查encourage的用法。encourage sb. to do sth.的被动语态形式就是sb. be encouraged to do sth.另外，此题还考查短语according to（按照）和strong points(长处，特长)。再根据其它提示。故翻译为：Young people should be encouraged to choose their careers according to their own strong points。 5．考查形容词短语作状语、定语从句以及find的用法。分析句子可知，本句为一般现在时，主语为I ，谓语为find， find oneself done表示“发现自己被…”,left behind是“被落在后面了”作宾语补足语。Being ignorant of the electronic products the students are talking about 为形容词短语作原因状语从句。products 为先行词，在后面的定语从句中，作talk about的