计算理论基础的问题证明：若一个集合的每一个子集都是上下文无关语言,那么这个集合是正则的.

计算理论基础的问题
证明：若一个集合的每一个子集都是上下文无关语言,那么这个集合是正则的.

Elements of the Theory of Computation 2nd Ed.)Harry R. Lewis, Christos H. Papadimitriou 编著 张立昂 刘田 译 计算理论是计算机科学的理论基础.本书介绍了计算理论最核心、最基本的内容,包括形式语言与自动机、可计算性和计算复杂性三大部分.全书共分七章,分别为：集合、关系和语言；有穷自动机；上下文无关语言；Turing机；不可判定性；计算复杂性；NP完全性.本书突出了算法,从而使计算机专业的学生更易于接受,也更有收益. 译者在译者序中写道：“我之所以愿意翻译这两本书,一是因为它们确实是两本关于计算理论的优秀教材；二是因为国内太缺乏这样的书了,尽管计算机类书刊极其繁多,可是计算理论的书却难觅踪影.”“特别希望立志致力于计算机科学技术事业的青年学生都来认真地学一点计算理论,那将可能是终身受益的.” 本书适合作为计算机专业及数学专业本科生或研究生的教材,也可供从事计算机科学的教学与研究人员参考. 前言： 看看你的周围,计算无处不在,无时不在,每一个人都计算,计算影响着所有的人.所以能够如此,是因为在过去的几十年中计算机科学家发现了很复杂的方法用来管理计算机资源,实现通讯,翻译程序,设计芯片和数据库,创造更快、更廉价、更容易使用、更安全的计算机和程序. 和所有的主要学科一样,计算机科学的成功实践建立在优美和坚实的基础之上.自然科学有一些基本问题,如物质的本质是什么?有机体生命的基础和起源是什么?计算机科学同样有它自己的基本问题：什么是算法?什么是能计算的?什么是不能计算的?什么时候可以认为一个算法是实际可行的?６０多年来(甚至从电子计算机出现之前就开始了)计算机科学家一直在考虑这些问题并且给出充满智慧的回答,这一切对计算机科学产生了深刻的影响. 本书的目的是介绍渗透在计算机科学中的这些基本思想、模型和结果,它们都是该领域的基本范例,它们有很多理由是值得学习的.首先,现代计算机科学中的很多东西直接或间接地以它们为基础——而其余的应该…….其次,这些思想和模型是漂亮、有力的,是数学建模的杰出例子,是有长久价值的.此外,它们更是历史的一部分,是我们这个领域的“共同潜意识”.不首先了解它们,是很难理解计算机科学的. 这些思想和模型在本质上是数学的,这大概不会让人感到奇怪.虽然计算机肯定是一个物理实体,但是同样肯定的是关于它的物理方面,如它的分子和它的形状,能够值得说的很少；对计算机最有用的抽象显然是数学的,论证这些抽象所必需的手段也一定同样是数学的.此外,实际的计算工作需要只有数学才能提供的铁的保证(希望我们的编译程序正确地翻译,应用程序最终停机,等等).但是,在计算理论中使用的数学与其他应用学科中使用的数学有很大的区别,它一般是离散的,在这里不强调实数和连续变量,而强调有穷集合和序列.它以很少几个基本的概念为基础,通过小心、耐心、仔细、一层一层地处理这些概念,勾画出它的能力和深奥之处——这很像计算机,在第１章将使你回想这些基本的概念和方法(其中有集合、关系和归纳法),介绍在计算理论中使用它们的风格. 第２章和第３章描述某些受限制的计算模型.它们能够完成一些非常特殊的字符串处理工作,例如回答一个给定的字符串是否出现在给定的正文中,如字punk是否出现在莎士比亚文集中,或者检查一个给定的括号字符串是否正好平衡——像()和(())(),而不是)()的样子.这些受限制的计算模型(分别叫做有穷自动机和下推自动机)竟然作为像电路和编译程序之类很普通的系统的非常有用和高度完善的部分出现在现实生活中.在这里它们为我们探索算法的一般的形式定义提供极好的热身练习.此外,看到由于增加或删除各种特性这些装置的能力如何增强和减弱(或者,更经常地是,保持不变)是有教益的.其中最值得注意的特性是非确定性,计算的这个迷惑人的特性既是重要的,又是(相当荒谬地)非现实的. 在第４章,我们研究算法的一般模型,其中最基本的模型是Ｔuring机以卓越的英国数学家和哲学家Alan Ｍ.Ｔuring (１９１２—１９５４)的名字命名.他在１９３６年发表的开创性的论文标志计算理论的诞生.Ｔuring也是人工智能和计算机下棋以及生物学中形态形成领域中的先驱者.在第二次世界大战中,他帮助破译德国海军密码Enigma.想更多地了解他迷人的一生(以及他最后悲惨地死在官方残忍和偏执的手中)请阅读《Alan Ｔuring: Ｔhe Enigma》,Andrew Ｈodges 著,New Ｙork: Ｓimon Ｓchuster,１９８３年.Ｔuring机是第２章和第３章中字符串处理装置的相当简单的推广,结果令人吃惊地成为描述任意算法的一般框架.为了证明这一点,即通常所说的Church Ｔuring论题,我们引入越来越复杂的计算模型(Ｔuring机更强的变种,还有随机存取Ｔuring机和递归定义的数值函数),并且证明它们在能力上全都完全等价于基本的Ｔuring机模型. 再下一章处理不可判定性.某些自然的明确的计算任务具有这种出人意料的性质,可以证明它们超出了算法能够解决的范围.例如,问你是否能用给定的若干种形状的砖铺整个平面.如果这些形状中包括一个正方形,或者甚至一个三角形,则答案显然是“能够”.但是,如果是几种稀奇古怪的形状,或者规定几种形状必须至少使用一次,那会怎样?这肯定是很复杂的问题,你想用机器给出回答.在第５章我们使用Ｔuring机的形式表示证明这个问题和许多其他问题是根本不可能用计算机解决的. 即使当一项计算任务能够用某个算法解决的时候,也可能不存在解决它的适当快的、实际可行的算法.在本书的最后两章,我们说明怎么用它们的复杂性对现实生活中的计算问题进行分类：某些问题能够在合理的,即多项式的时间界限内解决,而另一些问题似乎需要以天文速度,即指数地增长的时间.在第７章我们定义一个叫做NP完全的问题类,它们是一些普通的、实际的、但难得出名的问题(旅行商问题仅是它们中的一个).我们证明所有这些问题在下述意义下是等价的：如果它们中的一个有有效的算法,则它们每一个都有有效的算法.普遍地相信所有NP完全问题具有固有的指数复杂度；这个猜想是否实际上为真是著名的P≠NP问题,它是当代数学家和计算机科学家面临的最重要和最深刻的问题之一. 本书有很多篇幅是有关算法及其形式基础的.然而,大概你也意识到了,在今天的计算机科学教学计划中,算法课程,包括算法的分析和设计,相当地脱离计算理论的课程.在本书的现行版本中,我们试图恢复这门课程的某种统一性.结果是,本书对算法也提供了相当不错的介绍,只是有些专门和非传统.在第１章形式地介绍算法及其分析,并且在第２章和第３章研究受限制的计算模型和由它们产生的自然的计算问题的时候一再重新提起.这样一来,在后面探索算法的一般模型的时候,读者处在较好的位置,能正确评价这种探索的目标并且断定是能成功的.在讲解复杂性时算法同样担任主角.因为鉴别复杂问题的最好方法是把它与另一个经得起有效算法考验的问题进行比较.最后一章用一节叙述对付NP完全性作为结束,给出在遇到NP完全问题时已经成功地使用过的算法技术(近似算法、穷举算法、启发式局部搜索等). 计算是必不可少的、有力的、优美的、具有挑战性和不断发展的——它的理论也是如此.本书仅讲了一个激动人心的故事的开头,它是对从计算理论宝库中精选出的少量基本论题的朴素介绍.我们希望它将激发读者去作进一步的探索,每一章最后的参考文献指出了好的出发点. 目录： 译者序(Ⅲ) 第一版序言(Ⅴ) 第二版序言(Ⅶ) 导言(Ⅸ) 第１章集合、关系和语言(１) １ １集合(１) １ ２关系与函数(４) １ ３特殊类型的二元关系(７) １ ４有穷集合与无穷集合(１１) １ ５三个基本的证明技术(１３) １ ６闭包与算法(１７) １ ７字母表与语言(２５) １ ８语言的有穷表示(２９) 参考文献(33) 第２章有穷自动机(３４) ２ １确定型有穷自动机(３４) ２ ２非确定型有穷自动机(３９) ２ ３有穷自动机与正则表达式(４７) ２ ４正则语言与非正则语言(５４) ２ ５状态最小化(５８) ２ ６关于有穷自动机的算法(６５) 参考文献(７０) 第３章上下文无关语言(７２) ３ １上下文无关文法(７２) ３ ２语法分析树(７９) ３ ３下推自动机(８３) ３ ４下推自动机与上下文无关文法(８７) ３ ５上下文无关语言与非上下文无关语言(９２) ３ ６关于上下文无关文法的算法(９７) ３ ７确定性与语法分析(１０２) 参考文献(１１５) 第４章Ｔuring机(１１７) ４１Ｔuring机的定义(１１７) ４ ２用Ｔuring机计算(１２５) ４３Ｔuring机的扩充(１３０) ４ ４随机存取Ｔuring机(１３６) ４ ５非确定型Ｔuring机(１４４) ４ ６文法(１４８) ４ ７数值函数(１５１) 参考文献(１５８) 第５章不可判定性(160) ５１Church Ｔuring论题(160) ５ ２通用Ｔuring机(161) ５ ３停机问题(163) ５ ４与Ｔuring机有关的不可判定问题(166) ５ ５与文法有关的不可解问题(168) ５ ６不可解的铺砖问题(172) ５ ７递归语言的性质(174) 参考文献(178) 第６章计算复杂性(179) ６１P类(179) ６ ２若干问题(181) ６ ３布尔可满足性(187) ６４NP类(190) 参考文献(194) 第７章NP完全性(196) ７ １多项式时间归约(196) ７２Cook定理(202) ７ ３其他的NP完全问题(207) ７ ４对付NP完全性(218)
麻烦采纳,谢谢!