大工20秋《编译原理基础》辅导资料六

作业辅导

编译原理基础辅导资料六
主    题：第二章词法分析
学习时间：2020年11月2日--11月8日“不忘初心、牢记使命”主题理论学习：
我们党要始终成为时代先锋、民族脊梁，始终成为马克思主义执政党，自身必须始终过硬。全党要更加自觉地坚定党性原则，勇于直面问题，敢于刮骨疗毒，消除一切损害党的先进性和纯洁性的因素，清除一切侵蚀党的健康肌体的病毒，不断增强党的政治领导力、思想引领力、群众组织力、社会号召力，确保我们党永葆旺盛生命力和强大战斗力。
摘选自《决胜全面建成小康社会，夺取新时代中国特色社会主义伟大胜利》内    容：
我们这周主要学习第二章词法分析DFA化简、词法模式的识别过程、子集构造法的相关内容，希望通过下面的内容能使同学们加深对本章相关知识点的理解。
教学目标：
能够理解词法分析概念
重点和难点：
重点
  正规式
  状态转换图
  有限自动机
  DFA构建
  子集构造法
   DAF化简
难点
有限自动机
正规式=>NFA=>DFA
先构造NFA，再将NFA转换为DFA
三大步骤：
1. NFA构建
2. NFA -> DFA的转化
3. DFA化简
二、DFA的化简


判断依据：状态的可区分性
状态的可区分性
存在串w，使得从状态s开始，对w进行状态转换，最终停在某个接受状态；而对于从t开始对w进行状态转换后，却停在某个非接受状态。






三、词法模式识别过程图








四、基于DFA构建识别程序


五、子集构造法


NFA=>DFA






六、有限自动机




本章练习题：选择题
1、与(a|b)*等价的正规式是（      ）。
A. (a*|b*)*     B. (a|b)+    C. (ab)*     D. a*|b*
答案：A
2、正规式M1和M2等价是指（      ）。
A. M1和M2的状态数相等
B. M1和M2的有向边条数相等
C. M1和M2所识别的语言集相等  
D. M1和M2状态数和有向边条数相等
答案：C
问答题
1、写出字母表∑={a, b}上语言L={w| w中a的个数是偶数}的正规表达式，并给出接受该语言的最小状态DFA。
答案：
(b*ab*ab*)*b*


拓展资料
北大牛人唐翔(贴一篇文章激励一下)想必很多人都看过这篇文章吧。我也是很久以前就看过，今天看见这篇文章，顺便转给大家。    唐翔是我认识的最牛的人。这句话得好好解释一下：首先，什么叫做认识？认识当然指的是相互关系。比如说，我的老板姜伯驹和王诗宬，一个是两院院士，一个是长江学者，都曾获得过陈省身数学奖。我当然跟他们彼此认识，甚至可以说熟悉。那他们有没有唐翔牛呢？窃以为没有。又比如说，我还是见过几位当代一流数学家的：    陈省身、丘成桐、Smale、Atiyah，但他们根本不知道我是何许人，所以他们不能算我认识的人。那他们有没有唐翔牛呢？我觉得不好比较。不光是我觉得不好比较，很多人都有类似的感觉。有一次老谢（这是一个精通数学物理和数论的家伙）说：“二十世纪中国最伟大的三位数学家是陈省身、华罗庚、唐翔。”“不对！”何旭反驳道。这位几个月后将坐在MIT里研究李群的表示论的好吃懒做的不敢吃辣的重庆人意味深长地说道：“应该是唐翔、陈省身、华罗庚。”    另外一个需要澄清的概念是“牛”。很多认识唐翔的人都认为，唐翔除了数学牛以外，再没什么长处了。但我这里说的“牛”是把各个方面：数学、物理、化学、语文、外语、泡mm、灌水、切星际……都加到一起。在每个领域中定义一个牛指标，然后把它们生加到一起。我将之称为“综合牛指标”。所谓某甲比某乙牛，就是说某甲的综合牛指标大于某乙的综合牛指标。容易证明，我认识的其他人的综合牛指标都是有限数，但唐翔在数学领域的牛指标是趋于+∞的，而他在别的领域的牛指标至少是非负数，所以唐翔的综合牛指标大于我认识的其他人的综合牛指标，也就是说唐翔是我认识的最牛的人。证毕。    对于一个学数学的人来说，认识唐翔是他的不幸。这个不幸很不幸地降临在了96级数学系除了唐翔以外的师兄师姐们身上，也降临在了97级数学系大部分同仁的身上。我的不幸始于大二下学期。那时我们年级好多人都一窝蜂地去选大三的拓扑课，我也跟着去选，然后就认识了唐翔。唐翔身材魁梧，膀大腰圆，戴眼镜，坐前排，听讲非常认真。看不出来是一个牛人，因为通常牛人都是不大听课的，比如我的偶像Smale，据说大学期间常翘课，而且经常坐在台阶上很深沉地望着夕阳。    我们年级有一位mm也选了拓扑课，也总坐在前排，于是乎就经常向唐翔请教问题，没想到两年后这位mm会成为唐翔的gf……当然这位mm跟唐翔大概并不是在拓扑课上认识的，因为两年后这位mm会成为唐翔的gf……当然这位mm跟唐翔大概并不是在拓扑课上认识的，因为他们都担任一定职务，平时可能经常一起开会什么的。至于其中细节我并不大清楚，所以还是不说的好。但可以肯定的是，唐翔泡mm的牛指标是一个充分大的正数。    一学期转眼就过去，期末考试的时候，尤承业出题照例很简单，但对于我这种头脑不灵活的人来说做起来就很是费劲了。考完后出考场，我跟唐翔聊起试题，说有一小题没做出来。唐翔说：“很简单呀，这是书上一道习题，你把……”三言两语就把做法讲清楚，顿时让我感觉一学期的拓扑课算是白上了。    那时候才发现原来唐翔是个牛人，后来又陆续听到各种有关他的传说。一个流传很广的说法称，唐翔是一个绝对的完美主义者。有一次他考泛函，一个地方可能被扣1分，于是痛苦了一下午；还有一次他考测度论，一个地方可能被扣2分，于是别扭了一整天。通常来说，如果有一次数学考试连唐翔都没有得满分，那这次考试最后的成绩一定要经过若干次开方乘10的处理。也有人说唐翔的长处是记忆力好，所以他即使政治考试分数也很高。最后算平均分的时候，唐翔的各科成绩（包括政治）平均起来超过了95分。    我以前上高中的时候，老师经常跟我们说他以前的某个学生在北大数学系期间有七门功课是满分，创了北大的纪录。到了北大后，才觉得他十有八九是在吹牛，因为七门满分不大可能是北大数学系的纪录。不过我相信唐翔的13门功课满分一定是纪录。有一次我曾很不幸地看到了唐翔的成绩单的一页，在一堆100分中很刺眼地夹杂着一个90分，仔细一看，那门课"Probability?Theory"，主讲教师为"Qian?Minping".其实13门专业课满分并不能说明一个人的数学有多牛，充其量只能说明他很会考试。比如说99级一个师弟现在的专业平均分是99.x，还有一个师妹的专业平均分是98.x，虽然这样高的分数我考不出来，但光凭这个也不能让我佩服。因为大一大二的基础课还比较简单，数分高代解几等课程要拿满分也不算太困难，另外陆果的物理课又纯属是考背书，所以分数高一点儿并不奇怪。而唐翔的长处就是大一的时候还不很突出，大二起就习惯于考满分了。另外，考试考得好跟研究作得好是两回事，这一放之四海而皆准的真理早已为无数事实所证明。像Smale从小数学成绩就不突出，上大学时系主任追着要他退学。还有John?F.Nash，自小就被目为天才，但他参加两次普遍特别难的数学竞赛，都没进前五名，备受打击，连Harvard的offer都不敢要。到如今，谁还记得当年的前五名呢？    所以说虽然唐翔成绩好，但还不能成为让人佩服的理由。打个不太恰当的比方，就像是中国足球队友谊赛灭了无数强队，但也没人因此把你当根葱。    大二下学期末的时候，听说周民强金盆洗手，下学期的实变课改由一位年轻老师教。无庸隐讳，这位年轻老师科研虽然不错，但讲课肯定比不上有三十多年实变教学经验的强强。那会儿我正感觉前两年虚度时光，所以决心暑假待在学校，疯狂自学实变，下学期就找老师要求免修。没日没夜地读书、做题，最后书上的习题大概还剩下不到十题没做出来，自我感觉非常之好，巨有成就感。那些没做出来的题，每道想的时间都超过了十个小时，最后不得不放弃好，巨有成就感。。一日从图书馆出来时遇见了唐翔，谈起自己近日来的活动，不免吹起了牛：“大概还剩不到十道题没做出来吧！”唐翔说：“很不错啊！那本书上的习题，我至今还没听说有谁能全部做完的。”我听后十分得意，顺势拿一道不会做的题，“虚心”向他请教。唐翔听后，不假思索地说道：“我现在记不太清楚了。这种题就用那个什么定理，Egorov定理吧，找一个函数逼近一下就行了。”我说：“Egorov定理是有条件的，得是有限测度的集合。”唐翔说：“你可以取一个□□□（以下略去若干字）”锵哉锵哉锵锵哉，一句话惊醒我梦中人！再回到图书馆一做，果然立刻就搞定了，而且用同样办法又解决了两三道题，另外以前有些我做得很麻烦的题，现在很简单就能做出来了。真是听唐翔一席话，胜读半月书啊！后来有什么问题做不出来，要是能碰见唐翔的话，就直接问他了。不过没敢跟他一起自习，因为怕得神经衰弱。而且好象跟牛人一起自习是mm的习惯……    按lonekite的说法，96、97级不少人都养成了问唐翔问题的习惯。老谢曾跟唐翔一起上过黎曼几何，他说唐翔脑子很活，做题时很不少想法。这大概确是真的吧。一般来说，一道题如果连唐翔都做不出来，那就是真做不出来了，当然偶尔也有例外，这是后话。    唐翔最让人佩服的是他的刻苦。每天早上六点他就起床，到图书馆自习，晚上11点从三教回来。四年如一日，从不间断。后来图书馆的门卫都认得他了，所以他不用证件也能进去。他曾告诉flying说自己每天工作的时间是16小时。    当代数学家里最刻苦的是Erdos，每天工作19个小时，其次就得数丘成桐这样的人了，但他们年轻时平均每天工作也达不到16个小时。这样算来，唐翔之刻苦实在是让人瞠目结舌。有一次，我们年级一个到MIT的家伙突出豪言：“我要是有唐翔那么刻苦，早就是博士了！”此言一出，众人均ft，然后无数臭鸡蛋烂土豆都向那人扔过去了。    flying声称唐翔到图书馆最晚的一次是他离开北大的前一天，那天早上7:20时flying看见他进入图书馆。不过我怀疑flying弄错了，因为那段时间我天天早上都在学五看见唐翔，我估计flying看见唐翔是他从学五吃完早饭后进入图书馆。   让人奇怪的是，尽管唐翔这样没日没夜地学习，但身体还那么好。   中午不睡觉也照样精神奕奕，晚上头一沾枕就能入睡，然后鼾声如雷。    我们这些人要是不午睡，自习或上课的时候必定犯困，看看唐翔，实在让人既羡且妒。有时跟唐翔比较起自习时间，发现差得实在太远，只好乘上一个午睡系数什么的，因为要是不午睡的话，学习效率会低得多。    唐翔在国内的时候就决定出去学非交换几何。Noncommutative?Geometry这门学科是近一二十年兴起的，发展得非常热闹，跟弦理论有密切联系。这东西到底讲什么的我也不清楚，只知道国内搞的人非常少，而Atiyah将它称为二十一世纪最有前途的两个数学分支之一。 大概算子代数在非交换几何中起到了重要的作用，正如交换代数是代数几何的基本语言一样。非交换几何领域里的头号牛人?Alain?Connes?当初就因为算子代数方面的工作获得的?Fields?奖。唐翔嫌自己的算子代数水平不高，就找了一本这方面的专著来读。那可是真正的学术专著，而非一般的入门教材。书名就特别长，又是"representations"，又是"*-Algebra"，又是"locally?compact?groups"的，总之都是正常人没法学懂的东西。    其实如果光是题目吓人倒也没什么，看看那本书吧：共两卷，加起来一千四百八十余页。这个数字是什么概念呢？G.W.Whitehead?写过一本臭名昭著的"Elements?of?HomotopyTheory"，厚七百四十多页，重一公斤。这书已经被圈内人士认为过于厚重，不适合当教材，只能作为工具书查一查。而唐翔看的那书，每一卷的厚度都和?Whitehead?的书相当！   据说唐翔把那本两卷的书分成了四个部分，每两个月看一部分，用了将近一年的时间全部看完。老谢说，每当他在图书馆看见唐翔啃那本书时，他就流汗。现在的人过于浮躁，一个个都恨不得两年就把本科课程学完，再用一年就写出博士论文，很少有人肯下苦功夫练一练基本功的。谁还会花上一年的时间，啃一本一千四百八十多页的书呢？    唐翔深受钱敏的赏识，后者把唐推荐给了丘成桐。据说发offer的那段日子，丘成桐不在学校，所以唐翔只被列入了?Harvard?的?waiting?list，尽管是第一位。后来唐翔waiting?不下去了，就去了?Berkeley，然后Harvard?的offer就来了……    个人认为，丘成桐没有招到唐翔，是丘的不幸而非唐翔的不幸。唐翔和丘成桐其实有很多相似之处：两人都有做数学的硬功夫，天资都不能算是太高，但都以刻苦而闻名。不同的是唐翔比丘成桐更刻苦，但丘比唐更有名，至少现在是这样。    顺带说一下，在Fields奖得主中，丘成桐的天资不算高，但刻苦程度绝对没几个人能比得上他。有人曾请陈省身评论几位当代数学家，问到某人时，陈说：“他很用功。”问到另外一人时，陈也说：“他很用功。”但问到丘成桐时陈不说话了，因为丘成桐的用功是出了名的。据说丘吃饭的时候也要想数学问题，想着想着连饭都吐出来了。丘如今五十多岁，早已功成名就，但每天仍工作八小时以上，系里所有的数学会议都参加。另外他对自己的学生也极严格，要求每四天读一篇高质量的论文。可以想象，要是丘成桐得到了像唐翔这样刻苦的学生，一定会喜极而泣。    唐翔到了?Berkeley，导师是?Weinstein，----也是陈省身的学生和钱敏的朋友。Weinstein是搞?Poisson几何的，对非交换几何估计肯定不懂，要是丘成桐得到了像唐翔这样刻苦的学生，一定会喜极而泣。所以在那里是他教唐翔?Poisson几何，而唐翔教他非交换几何。自然唐翔的非交换几何是自学的，以他的算子代数功底和刻苦程度，要自学这种东西肯定是小菜一碟。唐翔写信回来说，在?Berkeley?几乎人人看过的书都比他多。那是自然，想来也没有谁会花一年的时间看一本一千多页的书。有那一年的时间，牛人们肯定至少看完了几十本书了。不过一年看几十本书的只是小牛，唐翔才是真的大牛。                                                   （完）
本内容由易百教育整理发布
网址www.openhelp100.com
QQ 515224986