形式语言与自动机课件

形式语言与自动机形式语言与自动机形式语言与自动机形式语言与自动机理论为什么学？

学什么？

怎么学？计算机科学与技术专业人员的4种基本专业能力：

（1）计算思维能力；

（2）算法的设计与分析能力；

（3）程序设计和实现能力；

（4）计算机软硬件系统的认知、分析、设计与应用能力。引言“在日常教育过程中，我们的老师，特别是班主任，一个动作，一种眼神，一句话语都会在学生心里产生意想不到的影响，但很少有人去注意这些细节，更不用说去注意由这些细节造成的失误与伤害了。”这段叙述中提到了“细节”这一问题。但我们所说的教学细节这一概念，不是上述的细节概念，而是在学习新知识点处，训练能力点处，体验情感点处的教学细节设计，简称“细节设计”。“细节设计”这一概念强调三个观点：1.教学细节是构成课堂的基本单位，所以，课堂是若干个教学细节组成的。课堂的得失与成败，往往决定于课堂教学中的每个细节的落实上。2.教学细节短小精悍，便于教师钻研和突破。要提高课堂教学实效，从细节设计入手，最为有利。3.在课堂教学实践中，忽视细节，教学不到位，教学效率低下，质量达不到，导致课改表面化，是当前课堂教学的通病。因此，强化教学细节设计的研究――提高课堂教学的实效，是当前教改的深化，是课程改革的深化。那么，什么样的细节设计是好的，是有实效性的呢？我们提出，细节设计必须具备三个特征，才是成功的细节设计，才能很好的完成教学任务，才能提升教学现场的品位，才能开掘教学的深层意蕴，才能实现教学的潜在意义。这三个特征是：教学细节的过程性、完整性特征；教学细节的主导性、互动性特征；教学细节的层次性、深刻性特征。一、教学细节必须是一个相对完整的学习过程，体现学习的过程性和完整性“细”我们可以理解为细小、精细。但是，我们绝对不能忽视教学细节的过程性和完整性。即使怎样细小的教学环节，也必须是一个完整的学习过程，在这个细节中，折射出学生对知识的理解由不懂到懂，对技巧的掌握由不会到会，由不熟练到熟练，对事物的认识由不全面到全面这一发展过程，这样的细节才是富有实效的细节。著名特级教师斯霞老师在引导一年级小学生理解“祖国”一词时设计了这样一个精练的教学细节：师：同学们，能告诉老师什么是祖国吗？生：祖国就是家乡。师：那么，我们的杭州市、长沙市就是我们的祖国了？生：老师，我知道了，祖国就是国家。师：美国、英国都是国家，我们能说美国、英国是我们的祖国吗？生：老师，祖国就是我们自己的国家。师：孩子们，你们说对了，祖国是我们自己的国家，是我们祖祖辈辈生长的地方。“祖国”一词，如果用语言解释，很抽象，学生不易理解，对于一年级孩子来说，难度更大。斯霞老师这一细节设计，用三次对话把祖国由“家乡”――升华到“国家”――再引领到“自己的国家”这一正确的含义。虽然师生只有三次简短的对话交流，却完成了对“祖国”一词正确而深刻地理解。这个细节就是一个完整的学习过程，既体现了学习的过程性，又体现了学习的完整性。二、教学细节必须是师生的互动组合，体现主导性和师生互动性新课程理念倡导“学生是课堂教学的主人”，“以学生为主体”是理想课堂的首要条件。但我们必须懂得教师的教，学生的学，不是空洞无物的，不是放手让学生自主就可以的。切不可以为新课改就是放手让学生去自学，教师可说说“请大家学习”、“请大家汇报”、“请大家收集、整理”就可以了。这样组织教学，师生之间没有真正意义上的互动，缺乏教师对学生思维的点拨，学生不能在师生互动的过程中提升认识水平。所以，我们强调，细节设计既要重视学生的主体性，又绝对不能忽视教师的主导作用。必须体现教师在关键处的指导和点拨，以引领学生的学习和思维不断向深入发展。现在我们来欣赏王崧舟老师对《荷花》一文中“冒”字的教学细节：师：请大家想一想，“冒”字还可以换成什么字？生：可以换成“长”。生：可以换成“钻”。生：可以换成“伸”。生：可以换成“露”。师：自己用心读读前后几句话，体会体会，怎样长出来才可以叫做冒出来。生：使劲地长。生：不停地长。生：笔直地长。师：你们再体会体会荷花长出来时的那种心情、那种状态，你觉得那是一种怎样的长？生：痛痛块块地长。生：争先恐后地长。生：兴高采烈地长。师：太好了！大家看，这就是从挨挨挤挤的荷叶之间喜气洋洋，生机勃勃地冒出来的白荷花（播放荷花课件）。你们想啊，这些白荷花冒出来以后想干什么呢？生：想看看外面这个精彩的世界。生：想吸一口新鲜的空气。生：想尽情展示自己的美丽。师：多么可爱的白荷花呀！一个“冒”字，不但把白荷花写活了，而且使白荷花更美了。这个教学细节，王崧舟老师紧紧抓住一个“冒”字，设计了四个层次反复引导，是教师主导，师生互动，使学生充分理解了白荷花那旺盛的生命力，美丽动人的姿态。这四个层次分别是：理解“冒”字字意；感悟生长状态；体会蓬勃生机；想象美丽心情。在这样层次清晰，步步深入的细节中，文本的思想感情如春风化雨，滋润学生心田，使学生不但受到了潜移默化的人文关爱，又学到了作者独具匠心的言语技能和技巧，实现了工具性和人文性的和谐统一。三、细节设计必须成功引导学生的学习思路，升华认知水平，体现层次性和深刻性有人对教学细节做过这样精僻地描述：细节犹如竹笋，每“剥”一层，便有一段“鲜活”呈现出来。教师若能一层一层“剥”下去，教学活动必将走向深入，课堂就会因此精彩纷呈。这段话生动地告诉我们：教学细节必须体现训练的层次性和深刻性，引领学生的学习思路；必须引领学生的思维，向深层次发展，提升学生的认知水平。在这个过程中，实现由独知向共鸣的转化，把学生的个性理解转化为全体学生的共性认识。一位教师教学《赤壁之战》时有这样一个精彩片段：指一名学生读：这一天，东南风很急，江面上波浪滔天。曹操正在船头迎风眺望，忽然有个士兵报告说：“江南隐隐约约有些船帆，趁着东南风向北岸驶来。”曹操定睛一看，果然有一队帆船直向北岸驶来……生：他把“江南隐隐约约有些船帆”这句中的“船帆”读成了“帆船”。师：是吗？你听得真仔细！谁还听出来了？生：学生纷纷举起手来。师：你们都听出来了！这段话中，前面是船帆，后面却是帆船，很容易读错的。你们想过没有，为什么士兵报告说江南隐隐约约有些船帆，而曹操看见的却是帆船呢？先自己想想，然后同桌交流交流自己的想法。生：我想“船帆”与”帆船”侧重点不同。“船帆”侧重于“帆”，“帆船”侧重于船。生：士兵看时一定是离得很远，只能隐隐约约看到船上的船帆，而曹操看时，他看到了带帆的船，说明船离得很近了。师：“船帆”给人印象远，“帆船”给人感觉近？有什么问题在里面？生：可以这样设想：曹操站在船头迎风眺望，他向远处看，一定没看到什么，可见东吴的船还没有出现；忽然兵士来报，也只是隐隐约约看到了船帆，可见东吴的船在水天相接处刚出现；可是当曹操定睛一看，已经清楚地看到了一队帆船，可见东吴的船速度太快了。师：可见东南风如何？生：风很大，浪很急，是巧借东南风。这个细节，教师在关键处充分发挥了自己的主导作用，以区别“船帆”与“帆船”的不同为切入点，调动学生深入思维，引导学生交流讨论，通过学生与教师的对话，与文本的对话，区别了两个词的不同之处，促进了学生的思维向准确性方向发展。同时又深入理解了课文，提升了认识水平。可以这样说：细节是在师生互动的过程中，培养学生综合素质的过程。细节设计的层次性和深刻性是引领学生的思维向深度和广度发展的重要条件，有利于提升学生的认识水平，提高学习效果。所以，必须重视细节设计的层次性和深刻性。我们再来欣赏一位教师在教学《飞夺卢定桥》最后一句时的精彩细节：师：同学们“浩浩荡荡”这个词你们看见过吗？知道它的意思吗？生：浩浩荡荡是说水势很大。师：不错，通常“浩浩荡荡”是用来说水势很大，汹涌澎湃，奔腾向前。但是在这个句子中，浩浩荡荡用来说谁呢？生：红军队伍。师：浩浩荡荡的红军队伍会有什么特点呢？生：红军人很多。师：人很多就可以说“浩浩荡荡”吗，集市上，赶集的人很多，摩肩接踵，我们可以说浩浩荡荡吗？生：（思考片刻）不能！“浩浩荡荡”有方向一致的意思。师：这回你们说对了，能具体完整地解释吗？生：“浩浩荡荡”是说：人很多，朝着同一方向前进。师：在这个句子中，“浩浩荡荡”是什么意思呢？生：壮大的红军队伍迈着整齐的步伐向抗日最前线出发了。师：从“浩浩荡荡”这个词中，你感觉到什么？生：红军战士精神焕发，信心百倍。生：这样的红军队伍一定会取得抗日战争的最后胜利。这个教学细节，分四个层次，很好地完成了教学任务。1.引导学生根据已有经验理解“浩浩荡荡”的本意――水势大。2.理解“浩浩荡荡”的引申意――形容人多。3.体会“浩浩荡荡”在本句中的意思――抗日的人多，心齐。4.感悟句子内涵――人心所向，抗日必胜！这样的教学设计在不断地提升学生的认知水平，发展了学生的思维品质，具有层次性和深刻性。总之，我们倡导的细节设计之细节，是就解决某一个问题而精心设计或生成的一个相对完整而短小的教学过程或学习过程，而不是教学过程中产生的瞬间的一个动作，一个眼神，一句话，一个亮相这种狭义的理解。细节人人做，但只有符合上述三个特征的细节设计，才有实效，才能叫得上好！近年来，江宁区横溪街道社区教育工作者结合区域特点，加大与科研院所和大专院校的合作，积极开展农科教结合富民教育课题的理论研究和实践探素，有力地推动了街道农业产业化和特色化发展。农科教结合富民教育的模式农科教结合。农：泛指农业和农村经济；科：指科学技术，特别是科技的应用、推广和普及；教：泛指教育，包括普通教育、职业技术教育、成人教育和部分高等教育。农科教结合，指通过开展教育培训来提高劳动者素质，把先进科学技术运用到生产实践中，从而使新品种、新技术迅速普及推广，使农业增效、农民增收。富民教育：指辖区市民经过各种技能培训，通过劳动经济富裕、身心愉悦、更有尊严的过程。农科教结合的模式：1.科技培训型。大面积、高质量地培训农民、传播科技，引导农民致富。2.政府统筹型。由政府牵头，成立农科教协会，制定相关优惠扶持政策，帮助农民致富。3.基地示范型。通过高标准建设农业科技示范基地，多渠道、多层次培训人才，带动农民致富。4.社会化服务型。为广大农民提供各种技术服务和培训，促进农民致富。5.公司+农户型。通过组建龙头企业，实现农户与市场的对接，扶持农民致富。6.科教兴村型。通过科教兴企，发展集体经济，带领农民共同致富。农科教结合富民教育的背景、意义目前，农业发展越来越受到资源和市场的双重约束，农业科技成果转化慢、农业效益比较低、农业劳动力大量过剩、农民收入增长缓慢等问题导致了诸多新的结构性矛盾。农村发展中的新形势、新情况，对农村成校发展农村教育工作提出了更高、更新的要求。我们认为科技教育是农村经济、社会持续发展的根本动力。农村成人教育，不单单是让农民掌握一门技术、求职或发家致富，更应以培养适应时代的新型农民为工作重点。而农科教结合，是我国广大科技教育工作者根据我国国情和农村实际，在多年的社会实践中摸索和总结出来的具有中国特色的农村教育与科技创新之路。它能解开农村成人教育与当地社会、经济发展互不相融的社会难题，优化科技、教育资源，形成合力，提高整体效益。其现实意义主要体现在以下几个方面：1.时代发展的需要《国务院关于积极实行农科教结合推动农村经济发展的通知》中明确指出：农科教结合是实现农业现代化的一个重要途径。实行农科教结合，在政府统筹协调下，使农、科、教等各有关方面形成强大合力，以促进农业和农村经济发展为目标，以推广先进农业科学技术为动力，以加强农村教育特别是职业技术教育和适用技术培训为基础，实现农业和农村经济的全面振兴。《江苏省国民经济和社会发展第十二个五年规划纲要》要求坚持走中国特色、江苏特点农业现代化道路，按照优质、高产、高效、生态、安全要求，积极推进农业规模化、产业化、标准化、信息化，大力发展现代农业，提高农业综合生产能力、抗风险能力、市场竞争能力。把农业和农村经济开发同科技开发、智力开发有机地结合起来，建立有利于科技、教育进步，振兴农业和农村经济的新机制，是当前农村深化改革的迫切任务。2.社区教育发展的需要社区教育应是及时、准确、真实地反映区域经济和社会发展需要的“本土化”教育，是大众化，普及化教育，也是休闲文化或者职业技能教育。社区教育的发展必须紧密结合街道建设与发展需要，以大力开展职业技术培训、再就业培训、职工转岗培训、外来人口培训为重点，成为三个文明的宣传阵地，广大居民（村民）的求知课堂，休闲健身文化的娱乐舞台，奔向小康的求富摇篮。横溪社区教育中心的省级农科教结合示范基地自从1999年创建以来，在新品种、新技术培训和推广、农村劳动力转移、大户牵小户共同富裕方面发挥了很大的作用，但是我们也清醒地看到，农科教结合面对纷繁复杂，变化多样的社区建设和社区教育需求，任何封闭式、围墙式、填鸭式、应试式、“正规式”学校教育已不能适应蓬勃发展的社区教育需要，如何使农科教结合培训活动内容丰富，按需教学、形式开放、受众广泛，让广大居民喜闻乐见，还有许多工作等待我们去研究、探索、实践。3.街道现实的需要近年来，横溪街道农民收入持续增长，但是增长的幅度不大。全面达小康，难点在增收，更在农民增收。街道通过论证，认为通过狠抓农业经济结构调整，努力打造城乡统筹发展第一街，都市美丽乡村第一街和生态休闲农业第一街，逐步把横溪打造成江宁区乃至南京南郊的农业特色旅游街镇是横溪“富民强街”的必由之路，为此，通过农科教结合，培养大批适应街道产业调整的劳动者成为当务之急。目标已定，就需要大批适应街道产业调整的劳动者，农科教结合就显得越来越重要。农科教结合富民教育的依据政策依据。《国家中长期教育改革和发展规划纲要（2010―2020年）》提出：加强基础教育、职业教育和成人教育统筹，促进农科教结合，培养有文化、懂技术、会经营的新型农民。理论依据。20世纪60年代，西方经济学家提出了人力资本的概念，强调教育在人力资本积累中的作用。著名经济学家舒尔茨在《改造传统农业一书》中指出，“在技术上优越的生产要素是农业增长的一个主要源泉的地方，就要考虑教育的重要性”。我国是一个农业大国，农业教育是整个社会主义教育事业的重要组成部分，离开了农业教育尤其是农民教育，就不可能有我国农业和农村的现代化。横溪街道农科教结合富民教育的现状自2001年横溪西瓜节举办以来，横溪的特色农业拉动了农业旅游的发展，现代农业旅游带动了农产品规模化产业化的推进。近年来，横溪街道农业结构调整力度不断加大，与省农科院及南京市有关大专院校的合作不断加强，在农业信息、新技术、新品种推广方面均有较强优势。横溪社区教育工作者紧紧把握千载难逢的大好时机，巧妙借势运作，走出一条农科教结合的新路，对推动地区农业产业化、农业特色化、实施富民强街战略起到积极作用。横溪街道农科教结合已经有了很好的发展态势，但与全国农科教结合示范区相比，差距是明显的。特别是在管理体制、经费投入、政策配套等方面严重制约了农科教结合的深入和大范围推进，需要我们以科学务实的态度和创新的精神，加以探索和逐步解决。横溪街道农科教结合富民教育的措施1.强化示范基地建设，为广大农民致富提供可靠保证（1）紧紧依靠科技，密切与南京市蔬菜研究所、江苏省农科院合作，并作为他们的实验展示基地，积极引进和推广新品种、新技术；（2）切实加强对示范基地的领导，建立基地建设领导小组，由街道主要领导任组长，街道分管教育和农业的两位领导任副组长；由农服中心、企服中心、劳保所、财政所、科委、成人教育中心校等单位的领导任成员；（3）示范基地实行独立核算，确立经理负责制，负责基地项目的生产、经营、管理工作。聘请一大批专兼职技术人员，负责基地的技术指导、培训、研究等工作。2.强化技术推广力度，为广大农民致富提供学习平台农业产业化经营的基础是广大农户，主导产业（品）技术进步不仅取决于农业科研机构和龙头企业，还取决于广大农户能否真正掌握技术。横溪西瓜，正是通过新品种试验、新技术示范和辅导等，使广大农民掌握了实际操作技能，才得以推广。我们不断加强农业技术推广力度，充分利用横溪成人教育中心现有资源，密切与街道有关部门及相关企业、科研单位协作，为广大农民提供更多的学习机会、开展更好的农业技术培训，引导广大农民更快地致富。3.强化专业队伍建设，为广大农民致富提供技术指导充分发挥区域内各类专业人才的作用，以教师和各行各业的专业人员为对象，整合各条线的人才资源，组成质量较高，数量稳定的社区教育兼职教师和志愿者队伍。建立社区教育管理人员、专职教师、兼职教师和志愿者队伍数据库，形成区域内社区教育师资共享的机制。4.强化农科教结合，为广大农民致富提供具体服务农科教结合，包括农民素质教育、农技成果推广、农村社会化服务、科技致富带头人培育等。农科教结合，就是要把农业科技成果推广到田间地头，把工作做到农户心头，让广大农民自觉自愿的行动起来，享受科技带来的益处；农科教结合，就是要把各种有利因素结合起来，发展科技型的专业合作社，让广大农民致富有靠山。5.强化经营模式，为广大农民致富提供市场农业产业化是现代农业发展的方向，要适应新形势，就需要大力提高农民的组织化程度，建立健全农业的社会化服务体系和农产品市场营销体系，大力发展新型市场主体。为此，横溪街道成立了横溪绿桥、田野、先荣等瓜果专业合作社。合作社创建是近三四年的事，这一农民合作组织，引起了广大种植农户的极大兴趣，带动了当地农业产业的迅速发展，带动了周边地区上万农民致富。专业合作社在成长中，坚持“大户带小户”原则，把培训、产前、产中、产后服务作为运作主线，注册了“绿王大自然”、“苏田牌”等商标，通过“七个统一”等生产要求，帮助社员生产出符合现代市场需求的绿色农产品。其中绿桥专业合作社被授予江苏省农业产业化经营先进单位、江苏省20佳农民专业合作社、江苏省示范单位、江苏省四有合作经济组织、江苏省营销协会一百强、江苏省科技型农业专业合作社等荣誉称号。形式语言与自动机理论为什么学？

学什么？

怎么学？

自然语言：人与人之间交流的基本手段。如：汉语、英语、俄语、法语、…等人工语言：主要用于人与计算机之间的交流。如：程序设计语言（也有例外，如世界语）语言理论：

语言自然语言人工语言形式语言：研究自然语言和人工语言都必须遵循的一般规律研究字符串集合及其性质的学科Chomsky文法体系：4种类型的文法及其产生的语言正规文法RG——正规语言RL；上下文无关文法CFG——上下文无关语言CFL；上下文有关文法CSG——上下文有关语言CSL；无限制文法URG——递归可枚举语言r.e.。计算机处理的主要对象自动机理论：语言（形式语言）识别器

4种类型自动机与4类文法相对应

有限自动机FA——RL——RG

下推自动机PDA——CFL——CFG

线性界限自动机LBA——CSL——CSG

图灵机TM——r.e.——URG

语言的运算及性质证明。可计算性基本理论：判定问题与不可判定性形式语言（FormalLanguage）课程特点：

抽象和形式化；

既有严格的理论证明；又有很强的构造性；包含一些基本模型的建立、性质等。四、教材与教学参考书教材：吴哲辉《形式语言与自动机理论》，北京，机械工业出版社，2019年4月，¥20。主要参考书：１．J.Hopcroft,

J.D.Ullman,《IntroductiontoAutomataTheory,LanguageandComputation》California,Addison-WesleyPublishingCompany,1979.（2019年清华，影印版）

2．刘田译，自动机理论、语言和计算导论，机械工业出版社，2019，¥39。

3．蒋宗礼，形式语言与自动机理论，清华大学出版社，2019，¥28。（另带习题解答）另外的预备知识

1、关于集合及运算（并、交、差、有限集、无限集、幂集、笛卡尔乘积等）

2、关于二元关系（三歧性、等价关系、等价类等）

3、关于常用证明方法（演绎推导、反证、例证、数学归纳、构造证明等）

4、树和图的应用第1章语言及其表示

语言—某个字母表上满足某些特定条件的字符串的集合1.1字母表、串和语言字母表（Alphabet）：由字符组成的非空有限集，通常用∑表示。空集不能作为字母表无限集也不能作为字母表自然语言人工语言—例如：英语的字母表∑={a,b,…,y,z,A,B,…Y,Z,，,。,“，”,；}∑={0,1}也可以看作一个字母表，一个二进制数可看作这个字母表上的一个字符串。串（String）：由某字符表上的字符组成的有限序列。例如：0100101是字母表∑={0,1}上的一个串。串的长度：一个串中字符的个数。设x为字母表∑上的一个串，x的长度记为|x|。例如|0100101|=7空串：不含任何字符的串，即长度为零的串，记为。前缀、后缀、子串串的逆：把一个串中的字符逆向顺序重新排列得到的另一个串设x为一个串，x的逆记为xR

例：若x=0100101

则xR=1010010

易知1）|xR|=|x|

2）空串的逆仍是空串：εR=ε串的连接（concatenation）运算串的幂运算串的连接运算又称为串的乘法运算。类似于从数的乘法运算推广到数的幂运算那样，也可以从串的乘法推广到串的幂运算。设x为一个串，则定义

代数系统间的同构关系语言（Language）语言几种基本运算对语言的理解句型、推导与句子文法所产生的语言举例举例1.3语言识别器

语言识别器同文法一样，都是对（可能为无限集的）语言提供有限表示的一种方式。语言识别器也称为自动机。如果说文法是从产生语言的角度来表示语言，那么自动机是从识别语言的角度来表示语言。自动机的结构可以大致表示成下图的形式。辅助存储器a1a2an…有限状态控制器图1.1自动机的大致结构即自动机由３部分组成：有限状态器、输入带和辅助存储器。有的自动机可以没有辅助存储器。输入带可以有限长或无限长，有限状态控制器对输入带可以只允许读，不允许写，也可以读和写。根据不同的规定，自动机可以分为几种类型。第2章正规表达式、正规文法与有限自动机

正规语言是Chomsky文法体系中最简单的一类语言。产生这种语言的文法是正规文法，识别这类语言的是有限自动机。此外，这类语言也可以用正规表达式表示。因此，正规语言也叫正规集。

2.2正规文法和正规语言

正规文法是Chomsky文法体系中最简单的一种文法。说它简单，是指它的产生式的形式简单，因为产生式集是一个文法的核心。

△定义和例子

2.3有限自动机（finiteautomaton,FA）2.8正规表达式和有限自动机的应用

许多控制系统的控制部件都是时序电路。对于一个控制系统，可以把它的时序电路转化为一个带输出的有限自动机来分析系统的运行。反过来，要设计一个复杂的控制系统，可以先设计出能够实现所要求得有限自动机，然后把它转化为时序电路。本节主要讨论两个问题：1）怎样用一个有限自动机描述一个时序电路？2）怎样用一个时序电路来实现一个有限自动机。用有限自动机描述时序电路我们对前面给出的时序电路的轮廓模型来加以说明。由于x1,…

，xn是一组输入信号，所以有限自动机的输入字母表为

∑={0，1}ny1,…,yk可以看作是系统的当前状态，加工后得到的w1,w2,…,wk，则是系统的下一状态，从而系统的状态集为

Q={0，1}kz1,…,z2是系统的输出信号，所以输出字母表为

△={0，1}m这样，我们就得到一个带输出的有限自动机

用时序电路实现有限自动机

把M1中的状态看作为k位逻辑值，输入字符看作为n位逻辑值，输出字母看作是m位逻辑值，这样状态转换函数和输出函数都可以用逻辑表达式表示，最后，就可以用逻辑电路（时序电路）来实现这些逻辑公式。下面通过一个例子来说明用时序电路实现带输出的有限自动机的全过程。s1s2xu1u2t1t200000010011000010010001100111000000101101011001101111000第3章上下文无关文法与下推自动机3.1上下文无关文法（context-freegrammer）

3.2推导树（derivationtree）

3.3上下文无关文法的化简

3.4乔姆斯基范式和格雷巴赫范式

3.5上下文无关语言的固有歧义性第4章图灵机4.2图灵机的基本概念4.3图灵机用于计算整函数

4.5变型图灵机

除了定义4.1中给出的图灵机的基本模型以外，图灵机还可以有许多